在将中缀表达式转换为后缀表达式的同时处理括号

我正在从事一个Java项目，需要我将中缀表达式转换为后缀表达式。 我目前能够将中缀表达式转换为后缀与这个方法，只要他们不包含括号，但我不知道如何处理括号。

基本上，我有两个堆栈，其中包含名为“令牌”的对象。 Token是一个包装类，它包含一个字符串，该字符串可以是一个数字，一个变量（被作为一个数字来计算，在用户输入时被挂起），运算符（运算符有一个与它相关的优先级，以便我的方法可以决定如何处理“+”，“ – ”，“*”和“/”之间的操作顺序）或括号（括号可以确定是左括号还是右括号）。

我应该如何处理括号？ 那么多层括号呢？ 

public String toPostFix() { StringBuilder postfixstr = new StringBuilder(); Stack<Token> in_fix = new Stack<>(); Stack<Token> post_fix = new Stack<>(); for (int i = tokens.length - 1; i >= 0; i--) { t = new Token(tokens[i]); in_fix.push(t); } //there are still tokens to process while (!in_fix.empty()) { //is a number if (in_fix.peek().type == 1) { postfixstr.append(in_fix.pop().toString()); } //is an operator and the stack is empty else if (in_fix.peek().type == 3 && post_fix.empty()) { post_fix.push(in_fix.pop()); } // is an operator that has higher priority than the operator on the stack else if (in_fix.peek().type == 3 && in_fix.peek().isOperator() > post_fix.peek().isOperator()) { post_fix.push(in_fix.pop()); } // is an operator that has lower priority than the operator on the stack else if (in_fix.peek().type == 3 && in_fix.peek().isOperator() <= post_fix.peek().isOperator()) { postfixstr.append(post_fix.pop()); post_fix.push(in_fix.pop()); } //puts the rest of the stack onto the output string if (in_fix.empty()) { while (!post_fix.empty()) { postfixstr.append(post_fix.pop()); } } } return postfixstr.toString(); }

您需要将左括号推入堆栈，并在遇到右括号时像这样处理堆栈： 

 // opening ( if (in_fix.peek().type == 4) { post_fix.push(in_fix.pop()); } //closing ) if(in_fix.peek().type == 5){ while(!(post_fix.isEmpty() || post_fix.peek().type == 4)){ postfixstr.append(post_fix.pop()); } if (post_fix.isEmpty()) ; // ERROR - unmatched ) else post_fix.pop(); // pop the ( in_fix.pop(); // pop the ) }

试试这个方法： 

  //opening Parenthesis if (in_fix.peek().type == 4) { post_fix.push(in_fix.pop()); } //closing Parenthesis if(in_fix.peek().type == 5){ //Till opening parenthesis encountered in stack, append operators to postfix. and pop parenthesis and do not append to post_fix. while(post_fix.peek().type!=4){ postfixstr.append(post_fix.pop()); } //finally pop left parenthesis from post_fix stack. post_fix.pop(); }

我推荐的是：

  • 做一个搜索加括号的表达式的外部搜索。
  • 在该子表达式上运行该过程，直到获得结果。
  • 将括号内的表达式替换为结果的编号。
  • 重复，直到所有括号表达式被替换。 
 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class InfixTopostFix { public static void main(String argv[]) throws IOException { String infix; InfixTopostFix converter = new InfixTopostFix(); //create an input stream object BufferedReader keyboard = new BufferedReader(new InputStreamReader(System.in)); //get input from user System.out.print("\nEnter the algebraic expression in infix: "); infix = keyboard.readLine(); //output as postfix System.out.println("The expression in postfix is:" + converter.toPostfix(infix)); } private String toPostfix(String infixString) //converts an infix expression to postfix { char inputSymbol; String postfixOutput = ""; Stack<Character> operatorStack = new Stack<>(); for (int i = 0; i < infixString.length(); ++i) //while there is input to be read { inputSymbol = infixString.charAt(i); if (Character.isLetter(inputSymbol)) { postfixOutput = postfixOutput + inputSymbol; } else if (inputSymbol == '(') { operatorStack.push(inputSymbol); } else if (inputSymbol == ')') { while (operatorStack.peek() != '(') { postfixOutput = postfixOutput + operatorStack.pop(); } operatorStack.pop(); //remove '(' } else { while (!operatorStack.isEmpty() && !(operatorStack.peek() == '(') && prec(inputSymbol) <= prec(operatorStack.peek())) { postfixOutput = postfixOutput + operatorStack.pop(); } operatorStack.push(inputSymbol); } } while (!operatorStack.isEmpty()) postfixOutput = postfixOutput + operatorStack.pop(); return postfixOutput; } int prec(char x) { if (x == '+' || x == '-') return 1; if (x == '*' || x == '/' || x == '%') return 2; return 0; } }

将中缀转换为后缀的更简单的解决方案：如果当前字符是字母表，则将其附加到临时输出字符串运算符，弹出优先级等于或高于当前运算符的所有运算符（到临时输出字符串）然后将当前运算符推到右边，弹出所有运算符（到临时输出字符串），直到在左边的圆括号中找到左括号，然后将其推入堆栈

Interesting Posts