在将中缀表达式转换为后缀表达式时处理括号 [英] Handling parenthesis while converting infix expressions to postfix expressions

问题描述

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

I'm working on a project in Java that requires me to convert an infix expression to a postfix expression. I am currently able to convert infix expressions to postfix with this method as long as they don't contain parenthesis, but I can't figure out how to handle parenthesis.

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

Basically, I have two stacks that hold objects that are called 'Token'. A Token is a wrapper class that holds a string that is either a number, variable (which gets evaluated as a number, pending on user input), operator (the operator has a priority level associated with it so that my method can determine how to handle order of operations between '+', '-', '*' and '/'), or a parenthesis (the parenthesis has a way to determine if it is a open parenthesis or a closed parenthesis).

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

How should I handle parenthesis? What about multiple layers of parenthesis?

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

推荐答案

你需要向左推括号到堆栈上，并在遇到右括号时处理堆栈：

You need to push the left parenthesis onto the stack, and process the stack like so when you encounter a right parenthesis:

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

这篇关于在将中缀表达式转换为后缀表达式时处理括号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！