使用堆栈将中缀表达式转换成后缀表达式

Question

我需要编写一个程序，将中缀表达式转换为后缀表达式。但是当我使用括号时，遇到了问题。例如，当我输入"a + (c - h) / (b * d)"时，输出结果是"ac+h-b/d*"，而实际上应该是"a c h - 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());
    }
}

- Joe

---

你是否正在尝试实现Dijkstra的逆波兰式算法？ - jdphenix

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

- Naman Gala

---

这非常有帮助！我现在知道我哪里出错了。非常感谢！ - Joe

只是想帮忙。 - Naman Gala

Answer 2

你需要使用结合性和比较操作符优先级。我已经大部分涵盖了所有操作符。

先决条件 - 表达式应该通过空格 ' '进行拆分。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class Test{

    public static final int                LEFT_ASSOC      = 0;
    public static final int                RIGHT_ASSOC     = 1;
    public static final Map<String, int[]> ARITH_OPERATORS = new HashMap<String, int[]>();
    public static final Map<String, int[]> REL_OPERATORS   = new HashMap<String, int[]>();
    public static final Map<String, int[]> LOG_OPERATORS   = new HashMap<String, int[]>();
    public static final Map<String, int[]> OPERATORS       = new HashMap<String, int[]>();

    static {
        ARITH_OPERATORS.put("+", new int[] { 25, LEFT_ASSOC });
        ARITH_OPERATORS.put("-", new int[] { 25, LEFT_ASSOC });
        ARITH_OPERATORS.put("*", new int[] { 30, LEFT_ASSOC });
        ARITH_OPERATORS.put("/", new int[] { 30, LEFT_ASSOC });
        ARITH_OPERATORS.put("%", new int[] { 30, LEFT_ASSOC });
        ARITH_OPERATORS.put("^", new int[] { 35, RIGHT_ASSOC });
        ARITH_OPERATORS.put("**", new int[] { 30, LEFT_ASSOC });

        REL_OPERATORS.put("<", new int[] { 20, LEFT_ASSOC });
        REL_OPERATORS.put("<=", new int[] { 20, LEFT_ASSOC });
        REL_OPERATORS.put(">", new int[] { 20, LEFT_ASSOC });
        REL_OPERATORS.put(">=", new int[] { 20, LEFT_ASSOC });
        REL_OPERATORS.put("==", new int[] { 20, LEFT_ASSOC });
        REL_OPERATORS.put("!=", new int[] { 20, RIGHT_ASSOC });

        LOG_OPERATORS.put("!", new int[] { 15, RIGHT_ASSOC });

        LOG_OPERATORS.put("&&", new int[] { 10, LEFT_ASSOC });

        LOG_OPERATORS.put("||", new int[] { 5, LEFT_ASSOC });

        LOG_OPERATORS.put("EQV", new int[] { 0, LEFT_ASSOC });
        LOG_OPERATORS.put("NEQV", new int[] { 0, LEFT_ASSOC });

        OPERATORS.putAll(ARITH_OPERATORS);
        OPERATORS.putAll(REL_OPERATORS);
        OPERATORS.putAll(LOG_OPERATORS);
    }

    public static void main(String args[]) {
        String inputExpression = "a + ( c - h ) / ( b * d )";

        String[] input = inputExpression.split(" ");
        List<String> output = infixToRPN(input);
        System.out.println(output.toString());
    }

    private static boolean isAssociative(String token, int type) {
        if (!isOperator(token)) {
            System.out.println("");
        }
        if (OPERATORS.get(token)[1] == type) {
            return true;
        }
        return false;
    }

    private static boolean isOperator(String token) {
        return OPERATORS.containsKey(token);
    }

    private static int cmpPrecedence(String token1, String token2) {
        if (!isOperator(token1) || !isOperator(token2)) {
            System.out.println("");
        }
        return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];
    }

    private static ArrayList<String> infixToRPN(String[] inputTokens) {
        ArrayList<String> out = new ArrayList<String>();
        Stack<String> stack = new Stack<String>();
        // For all the input tokens [S1] read the next token [S2]
        for (String token : inputTokens) {
            if (isOperator(token)) {
                // If token is an operator (x) [S3]
                while (!stack.empty() && isOperator(stack.peek())) {
                    // [S4]
                    if ((isAssociative(token, LEFT_ASSOC) && cmpPrecedence(token, stack.peek()) <= 0)
                            || (isAssociative(token, RIGHT_ASSOC) && cmpPrecedence(token, stack.peek()) < 0)) {
                        out.add(stack.pop()); // [S5] [S6]
                        continue;
                    }
                    break;
                }
                // Push the new operator on the stack [S7]
                stack.push(token);
            } else if (token.equals("(")) {
                stack.push(token); // [S8]
            } else if (token.equals(")")) {
                // [S9]
                while (!stack.empty() && !stack.peek().equals("(")) {
                    out.add(stack.pop()); // [S10]
                }
                stack.pop(); // [S11]
            } else {
                out.add(token); // [S12]
            }
        }
        while (!stack.empty()) {
            out.add(stack.pop()); // [S13]
        }
        return out;
    }
}

输出

[a, c, h, -, b, d, *, /, +]

- Ankur Singhal

---

这并没有帮助解决现有代码中的问题。 - Naman Gala