java - 使用堆栈将 Infix 转换为 Postfix

Question

这个问题已经有答案了:

Handling parenthesis while converting infix expressions to postfix expressions (2 个回答)

已关闭 6 年前。

我必须编写一个程序，将用中缀表示法编写的表达式更改为后缀表示法。当我开始使用括号时遇到问题。例如，当我输入“a + (c - h)/(b * d)”时，它会显示为“ac+h-b/d*”，而它应该显示为“a ch - b d */+”。非常感谢您的帮助。谢谢。

import java.util.Scanner;
import java.util.Stack;

public class PostfixConverter {
    static private String expression;
    private Stack<Character> stack = new Stack<Character>();

    public PostfixConverter(String infixExpression) {
        expression = infixExpression;
    }

    public String infixToPostfix() {
        String postfixString = "";

        for (int index = 0; index < expression.length(); ++index) {
            char value = expression.charAt(index);
            if (value == '(') {

            } else if (value == ')') {
                Character oper = stack.peek();

                while (!(oper.equals('(')) && !(stack.isEmpty())) {
                    stack.pop();
                    postfixString += oper.charValue();

                }
            } else if (value == '+' || value == '-') {
                if (stack.isEmpty()) {
                    stack.push(value);
                } else {
                    Character oper = stack.peek();
                    while (!(stack.isEmpty() || oper.equals(('(')) || oper.equals((')')))) {
                        stack.pop();
                        postfixString += oper.charValue();
                    }
                    stack.push(value);
                }
            } else if (value == '*' || value == '/') {
                if (stack.isEmpty()) {
                    stack.push(value);
                } else {
                    Character oper = stack.peek();
                    while (!oper.equals(('+')) && !oper.equals(('-')) && !stack.isEmpty()) {
                        stack.pop();
                        postfixString += oper.charValue();
                    }
                    stack.push(value);
                }
            } else {
                postfixString += value;
            }
        }

        while (!stack.isEmpty()) {
            Character oper = stack.peek();
            if (!oper.equals(('('))) {
                stack.pop();
                postfixString += oper.charValue();
            }
        }
        return postfixString;
    }

    public static void main(String[] args) {
        System.out.println("Type an expression written in Infix notation: ");
        Scanner input = new Scanner(System.in);
        String expression = input.next();
        PostfixConverter convert = new PostfixConverter(expression);
        System.out.println("This expression writtien in Postfix notation is: \n" + convert.infixToPostfix());
    }
}

Answer 1

您提供的代码类似于 this 。但该代码也不起作用。

我已更新您的代码并添加了更改的注释。

import java.util.Scanner;
import java.util.Stack;

public class PostfixConverter {
    static private String expression;
    private Stack<Character> stack = new Stack<Character>();

    public PostfixConverter(String infixExpression) {
        expression = infixExpression;
    }

    public String infixToPostfix() {
        String postfixString = "";

        for (int index = 0; index < expression.length(); ++index) {
            char value = expression.charAt(index);
            if (value == '(') {
                stack.push('('); // Code Added
            } else if (value == ')') {
                Character oper = stack.peek();

                while (!(oper.equals('(')) && !(stack.isEmpty())) {
                    stack.pop();
                    postfixString += oper.charValue();
                    if (!stack.isEmpty()) // Code Added
                        oper = stack.peek(); // Code Added
                }
                stack.pop(); // Code Added
            } else if (value == '+' || value == '-') {
                if (stack.isEmpty()) {
                    stack.push(value);
                } else {
                    Character oper = stack.peek();
                    while (!(stack.isEmpty() || oper.equals(('(')) || oper.equals((')')))) {
                        oper = stack.pop(); // Code Updated
                        postfixString += oper.charValue();
                    }
                    stack.push(value);
                }
            } else if (value == '*' || value == '/') {
                if (stack.isEmpty()) {
                    stack.push(value);
                } else {
                    Character oper = stack.peek();
                    // while condition updated
                    while (!oper.equals(('(')) && !oper.equals(('+')) && !oper.equals(('-')) && !stack.isEmpty()) {
                        oper = stack.pop(); // Code Updated
                        postfixString += oper.charValue();
                    }
                    stack.push(value);
                }
            } else {
                postfixString += value;
            }
        }

        while (!stack.isEmpty()) {
            Character oper = stack.peek();
            if (!oper.equals(('('))) {
                stack.pop();
                postfixString += oper.charValue();
            }
        }
        return postfixString;
    }

    public static void main(String[] args) {
        System.out.println("Type an expression written in Infix notation: ");
        Scanner input = new Scanner(System.in);
        String expression = input.next();
        PostfixConverter convert = new PostfixConverter(expression);
        System.out.println("This expression writtien in Postfix notation is: \n" + convert.infixToPostfix());
    }
}