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

Question

在将infix表达式转换为后缀表达式时处理括号我正在使用Java开发一个项目，该项目要求我将infix表达式转换为后缀表达式。我目前能够使用此方法将infix表达式转换为后缀，只要它们不包含括号，但我不知道如何处理括号。基本上，我有两个堆栈，它们保存被称为“令牌”的对象。令牌是一个包装类，它包含一个字符串，该字符串要么是数字、变量(在用户输入时被计算为数字，待定)、运算符(运算符具有与其关联的优先级级别，以便使我的方法可以确定如何处理‘+’、‘-’、‘*’和‘/’之间的操作顺序，要么是括号(括号有确定它是开括号还是关闭括号)的方法。我该如何处理括号？多层括号呢？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();}

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

Answer 3

这个算法是Edsger Dijkstra在1961年发明的，这是其中一部分的精确表示。你的里程明显不同。