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

我正在开发一个Java项目，需要我将中缀表达式转换为后缀表达式。 我目前能够使用此方法将中缀表达式转换为postfix，只要它们不包含括号，但我无法弄清楚如何处理括号。

基本上，我有两个堆栈，其中包含称为“令牌”的对象。 令牌是一个包装类，它包含一个字符串，它是一个数字，变量（被评估为数字，等待用户输入），运算符（运算符具有与之关联的优先级，以便我的方法可以确定如何处理’+’，’ – ‘，’*’和’/’之间的操作顺序，或括号（括号有一种方法可以确定它是一个左括号还是一个闭括号）。

我该如何处理括号？ 多层括号怎么样？

public String toPostFix() { StringBuilder postfixstr = new StringBuilder(); Stack in_fix = new Stack(); Stack 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(); } 

Answer 1

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

 // 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 ) } 

Answer 2

试试这种方式：

  //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(); }