使用Stacks Java将中缀转换为Postfix
我正在尝试编写一个程序来将中缀表达式转换为后缀表达式。
我使用的算法如下：
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. 这是我的代码打印出错误的结果。
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 stack = new Stack(); 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")); } }
该程序应打印AB*CD+-E+但它正在打印AB*-CD+E 为什么输出不正确？
此外，是否有一个更优雅的解决方案来解决这个问题。 如果您有或者知道，请分享。
问题在于你的其他部分：
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);
因此，当您看到堆栈不为空且优先级匹配更高时，您将使用stack.push（）两次推送相同的c元素。
所以把这个stack.push放在else部分或从if条件中删除push。
另一个问题是，当最后你在堆栈中有一些操作符时，你不会弹出它们。
这是我为你的案例提出的代码：
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 stack = new Stack (); 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")); }
我认为以上答案是不正确的。
这是我更正的版本：
package Stack; import java.util.Stack; /* * Algorithm 1. Scan the infix expression from left to right. 2. If the scanned character is an operand, output it. 3. Else, …..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty), push it. …..3.2 Else, Pop the operator from the stack until the precedence of the scanned operator is less-equal to the precedence of the operator residing on the top of the stack. Push the scanned operator to the stack. 4. If the scanned character is an '(', push it to the stack. 5. If the scanned character is an ')', pop and output from the stack until an '(' is encountered. 6. Repeat steps 2-6 until infix expression is scanned. 7. Pop and output from the stack until it is not empty. */ public class InfixToPostFixEvalution { private static boolean isOperator(char c) { return c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '(' || c == ')'; } private static int getPrecedence(char ch) { switch (ch) { case '+': case '-': return 1; case '*': case '/': return 2; case '^': return 3; } return -1; } // A utility function to check if the given character is operand private static boolean isOperand(char ch) { return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'); } public static String convertToPostfix(String infix) { Stack stack = new Stack (); StringBuffer postfix = new StringBuffer(infix.length()); char c; for (int i = 0; i < infix.length(); i++) { c = infix.charAt(i); if (isOperand(c)) { postfix.append(c); } else if (c == '(') { stack.push(c); } // If the scanned character is an ')', pop and output from the stack // until an '(' is encountered. else if (c == ')') { while (!stack.isEmpty() && stack.peek() != '(') { postfix.append(stack.pop()); } if (!stack.isEmpty() && stack.peek() != '(') return null; else if(!stack.isEmpty()) stack.pop(); } else if (isOperator(c)) // operator encountered { if (!stack.isEmpty() && getPrecedence(c) <= getPrecedence(stack.peek())) { postfix.append(stack.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^de)^(f+g*h)-i")); } }
这段代码也在堆栈中插入“（”并相应删除。只是另一种实现中缀到后缀的方法。这里检查是直到我在堆栈中找不到低优先级运算符我会弹出值。例如，如果堆栈有 – 并且下一个运算符是+，它将弹出 – 因为它具有相同的优先级。
我已经添加了自定义堆栈实现，但是java提供的普通堆栈也可以使用到位
import chapter4.LinkedListStack(custom stack implementation); public class InfixToPostfix { public String infixToPostfix(String str) { LinkedListStack stack = new LinkedListStack<>(); String[] st = str.split(""); String result = ""; for (String s : st) { if (operator(s)) { if (")".equals(s)) { while (!stack.isEmpty() && !"(".equals(stack.getTop())) { result += stack.pop(); } if (!stack.isEmpty()) { stack.pop(); } } else { if (!stack.isEmpty() && !isLowerPrecedence(s, stack.getTop())) { stack.push(s); } else { while (!stack.isEmpty() && isLowerPrecedence(s, stack.getTop())) { String top = stack.pop(); if (!"(".equals(top)) { result += top; } } stack.push(s); } } } else { result += s; } } while (!stack.isEmpty()) { result += stack.pop(); } return result; } private boolean isLowerPrecedence(String s, String s1) { switch (s) { case "+": return !("+".equals(s1) || "(".equals(s1)); case "-": return !("-".equals(s1) || "(".equals(s1)); case "*": return "/".equals(s1) || "^".equals(s1) || "(".equals(s1); case "/": return "*".equals(s1) || "^".equals(s1) || "(".equals(s1); case "^": return "(".equals(s1); case "(": return false; default: return false; } } private boolean operator(String s) { return "+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s) || "^".equals(s) || "(".equals(s) || ")".equals(s); } public static void main(String[] args) { InfixToPostfix itp = new InfixToPostfix(); System.out.println("The Postfix expression for A*B-(C+D)+E is: " + itp.infixToPostfix("A*B-(C+D)+E")); System.out.println("The Postfix expression for 1+2*4/5-7+3/6 is: " + itp.infixToPostfix("1+2*4/5-7+3/6")); System.out.println("The Postfix expression for a+(b*c)/d is: " + itp.infixToPostfix("a+(b*c)/d")); } }
public class LinkedListStack { private Node head; private static class Node { E item; Node next; public Node(E item, Node next) { this.item = item; this.next = next; } } public void push(E item) { System.out.println("push: " + item); Node newNode = new Node<>(item, null); newNode.next = head; head = newNode; } public E pop() { if (isEmpty()) { System.out.println("stack is Empty -> empty stack exception"); return null; } System.out.println("pop: " + head.item); E data = head.item; head = head.next; return data; } public boolean isEmpty() { return head == null; } public E getTop() { return head.item; } }
我认为问题在于：
private static boolean isLowerPrecedence(char op1, char op2) { switch (op1) { ..... case '(': return true; ..... }
在’（’，’，false应该返回。