使用堆栈Java对Postfix进行混合 [英] Infix to Postfix using Stacks Java
本文介绍了使用堆栈Java对Postfix进行混合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我正在尝试编写一个将中缀表达式转换为后缀表达式的程序。
我使用的算法如下：
1 。创建一个栈
2.表达式中的每个字符t
- 如果t是一个操作数，将其附加到输出
- 否则如果t是'）'，然后从堆栈中弹出直到'（'遇到并将
附加到输出，不要附加'（'到输出
- 如果t是运算符或'（'
- 如果t有优先级高于堆栈顶部，然后将t
推送到堆栈
- 如果t的优先级低于堆栈顶部，则从堆栈中继续弹出
并附加到输出，直到任一堆栈
为空或遇到较低优先级的操作符
输入结束后，保持弹出并附加到输出，直到
堆栈为空
这是我的代码打印出错误的结果。
public class InfixToPostfix
{
private static boolean isOperator（char c）
{
返回c =='+'|| c ==' - '|| c =='*'|| c =='/'|| c =='^'
|| c =='（'|| c =='）';
}
private static boolean isLowerPrecedence（char op1，char op2）
{
switch（op1）
{
case'+' ：
case' - '：
return！（op2 =='+'|| op2 ==' - '）;
case'*'：
case'/'：
return op2 =='^'|| op2 =='（';
case'^'：
return op2 =='（';
case'（'：
return true;
默认值：
返回false;
}
}
public static String convertToPostfix（String infix）
{
堆栈< Character> stack = new Stack< Character>（）;
StringBuffer postfix = new StringBuffer（infix.length（））;
char c;
for（int i = 0; i
c = infix.charAt（i）;
if（！isOperator（c） ）
{
postfix.append（c）;
}
else
{
if（c =='）'）
{
while（！stack.isEmpty（）&& stack.peek（）！='（'）
{
pos tfix.append（stack.pop（））;
}
if（！stack.isEmpty（））
{
stack.pop（）;
}
}
else
{
if（！stack.isEmpty（）&&！isLowerPrecedence（c，stack.peek（） ））
{
stack.push（c）;
}
else
{
while（！stack.isEmpty（）&& amp; isLowerPrecedence（c，stack.peek（）））
{
Character pop = stack.pop（）;
if（pop！='（'）
{
postfix.append（pop）;
}
}
}
stack.push（c）;
}
}
}
return postfix.toString（）;
}
public static void main（String [] args）
{
System.out.println（convertToPostfix（A * B-（C + D）+ E））;
}
}
程序应打印 AB * CD + -E + / code>但是打印 AB * -CD + E 。
为什么输出不正确？
另外，有没有一个更优雅的解决方案来解决这个问题，请分享，如果你有或知道一个。
解决方案
问题是与你的其他部分：
if（！stack.isEmpty（）&！isLowerPrecedence（c，sta ck.peek（）））
{
stack.push（c）;
}
else
{
while（！stack.isEmpty（）&& amp; isLowerPrecedence（c，stack.peek（）））
{
Character pop = stack.pop（）;
if（pop！='（'）
{
postfix.append（pop）;
}
}
}
stack.push（c）;
所以这里你用同样的c元素推两个堆栈.push（）当你看到堆栈不是空的，并且优先级匹配更高。
所以把这个stack.push放在else部分或从if的情况下删除push。 / p>
另一个问题是，最后你在堆栈里有一些操作符，你不会弹出他们。
以下是我为您的案例提出的代码：
private static boolean isOperator（char c）
{
return c =='+'|| c ==' - '|| c =='*'|| c =='/'|| c =='^'
|| c = ='（'|| c =='）';
}
private static boolean isLowerPrecedence（char op1，char op 2）
{
switch（op1）
{
case'+'：
case' - '：
return！（op2 ==' '|| op2 ==' - '）;
case'*'：
case'/'：
return op2 =='^'|| op2 =='（';
case'^'：
return op2 =='（';
case'（'：
return true;
默认值：
返回false;
}
}
public static String convertToPostfix（String infix）
{
堆栈< Character> stack = new Stack< Character>（）;
StringBuffer postfix = new StringBuffer（infix.length（））;
char c;
for（int i = 0; i
c = infix.charAt（i）;
if（！isOperator（c） ）
{
postfix.append（c）;
}
else
{
if（c =='）'）
{
while（！stack.isEmpty（）&& stack.peek（）！='（'）
{
postfix.append pop（））;
}
if（！stack.isEmpty（））
{
stack.pop（）;
}
}
else
{
if（！stack.isEmpty（）&&！isLowerPrecedence（c，stack.peek（） ））
{
stack.push（c）;
}
else
{
while（！stack.isEmpty（）&& amp; isLowerPrecedence（c，stack.peek（）））
{
Character pop = stack.pop（）;
if（c！='（'）
{
postfix.append（pop）;
} else {
c = pop;
}
stack.push（c）;
}
}
}
}
while（！stack.isEmpty（） ）{
postfix.append（stack.pop（））;
}
return postfix.toString（）;
}
public static void main （String [] args）
{
System.out.println（convertToPostfix（A * B-（C + D）+ E））;
}
I am trying to write a program to convert an infix expression to a postfix expression.
The algorithm that I am using is as follows :
1. Create a stack
2. For each character t in the expression
- If t is an operand, append it to the output
- Else if t is ')',then pop from the stack till '(' is encountered and append
it to the output. do not append '(' to the output.
- If t is an operator or '('
-- If t has higher precedence than the top of the stack, then push t
on to the stack.
-- If t has lower precedence than top of the stack, then keep popping
from the stack and appending to the output until either stack is
empty or a lower priority operator is encountered.
After the input is over, keep popping and appending to the output until the
stack is empty.
Here is my code which prints out wrong results.
public class InfixToPostfix
{
private static boolean isOperator(char c)
{
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'
|| c == '(' || c == ')';
}
private static boolean isLowerPrecedence(char op1, char op2)
{
switch (op1)
{
case '+':
case '-':
return !(op2 == '+' || op2 == '-');
case '*':
case '/':
return op2 == '^' || op2 == '(';
case '^':
return op2 == '(';
case '(':
return true;
default:
return false;
}
}
public static String convertToPostfix(String infix)
{
Stack<Character> stack = new Stack<Character>();
StringBuffer postfix = new StringBuffer(infix.length());
char c;
for (int i = 0; i < infix.length(); i++)
{
c = infix.charAt(i);
if (!isOperator(c))
{
postfix.append(c);
}
else
{
if (c == ')')
{
while (!stack.isEmpty() && stack.peek() != '(')
{
postfix.append(stack.pop());
}
if (!stack.isEmpty())
{
stack.pop();
}
}
else
{
if (!stack.isEmpty() && !isLowerPrecedence(c, stack.peek()))
{
stack.push(c);
}
else
{
while (!stack.isEmpty() && isLowerPrecedence(c, stack.peek()))
{
Character pop = stack.pop();
if (pop != '(')
{
postfix.append(pop);
}
}
}
stack.push(c);
}
}
}
return postfix.toString();
}
public static void main(String[] args)
{
System.out.println(convertToPostfix("A*B-(C+D)+E"));
}
}
The program should print AB*CD+-E+ but it is printing AB*-CD+E.
Why is the output incorrect ?
Also, Is there a more elegant solution to this problem. Please share if you have or know one.
解决方案
Issue is with your else part:
if (!stack.isEmpty() && !isLowerPrecedence(c, stack.peek()))
{
stack.push(c);
}
else
{
while (!stack.isEmpty() && isLowerPrecedence(c, stack.peek()))
{
Character pop = stack.pop();
if (pop != '(')
{
postfix.append(pop);
}
}
}
stack.push(c);
So here you are pushing the same c element twice with stack.push() when you see stack is not empty and precedence match is higher.
So put this stack.push within else part or remove the push from if condition.
Another issue is, when at the end you have some operators within the stack you dont pop them out.
Here's the code that i came up with for your case:
private static boolean isOperator(char c)
{
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'
|| c == '(' || c == ')';
}
private static boolean isLowerPrecedence(char op1, char op2)
{
switch (op1)
{
case '+':
case '-':
return !(op2 == '+' || op2 == '-');
case '*':
case '/':
return op2 == '^' || op2 == '(';
case '^':
return op2 == '(';
case '(':
return true;
default:
return false;
}
}
public static String convertToPostfix(String infix)
{
Stack<Character> stack = new Stack<Character>();
StringBuffer postfix = new StringBuffer(infix.length());
char c;
for (int i = 0; i < infix.length(); i++)
{
c = infix.charAt(i);
if (!isOperator(c))
{
postfix.append(c);
}
else
{
if (c == ')')
{
while (!stack.isEmpty() && stack.peek() != '(')
{
postfix.append(stack.pop());
}
if (!stack.isEmpty())
{
stack.pop();
}
}
else
{
if (!stack.isEmpty() && !isLowerPrecedence(c, stack.peek()))
{
stack.push(c);
}
else
{
while (!stack.isEmpty() && isLowerPrecedence(c, stack.peek()))
{
Character pop = stack.pop();
if (c != '(')
{
postfix.append(pop);
} else {
c = pop;
}
}
stack.push(c);
}
}
}
}
while (!stack.isEmpty()) {
postfix.append(stack.pop());
}
return postfix.toString();
}
public static void main(String[] args)
{
System.out.println(convertToPostfix("A*B-(C+D)+E"));
}
这篇关于使用堆栈Java对Postfix进行混合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
