逆波兰表达式

声明： 本总结仅为个人学习总结，以防止遗忘而作，不得转载和商用。
Reverse Polish Notation,即后缀表达式,也称逆波兰表达式RPN
如:
中缀表达式: a+(b-c)d
后缀表达式: abc-d+
题目:
计算给定的逆波兰表达式的值.有效操作只有+-/,每个操作都整数
如:
"2", "1", "+", "3", "" : 9 = (2+1)*3
"4", "13", "5", "/", "+" : 6 = 4+(13/5)
分析:
1.若当前字符是操作数,则压栈
2.若当前字符是操作符,则弹出栈中的两个操作数,计算后仍然压入栈中
(1).若某次操作,栈内无法弹出两个操作数,则表达式有误
Java版本的实现一，按字符数组处理：

public static int reversePolishNotation(char[] cs, int size) {
        Stack<Integer> stack = new Stack<>();
        int a,b;
        char token;
        for(int i=0;i<size;i++){
            token = cs[i];
            if (!isOperator(token)) {
                stack.push(Character.getNumericValue(token));
            }else {
                b = stack.pop();
                a = stack.pop();
                if (token == '+') {
                    stack.push(a+b);
                }else if (token == '-') {
                    stack.push(a-b);
                }else if (token == '*') {
                    stack.push(a*b);
                }else {
                    stack.push(a/b);
                }
            }
        }
        return stack.peek();
    }

是否是运算符:

public static boolean isOperator(char token) {
        return token == '+' || token == '-' || token == '*' || token == '/';
    }

测试代码:

public static void main(String[] args) {
        String string = "21+3*";
        char[] cs = string.toCharArray();
        int value = reversePolishNotation(cs, cs.length);
        System.out.println(value);
    }

输出结果：9
Java版本实现二，按字符串数组处理：

public static int reversePolishNotation(String[] str) {
        Stack<Integer> stack = new Stack<>();
        int a,b;
        String token;
        for(int i=0;i<str.length;i++){
            token = str[i];
            if (!isOperator(token)) {
                stack.push(Integer.parseInt(token));
            }else {
                b = stack.pop();
                a = stack.pop();
                if (token.equals("+")) {
                    stack.push(a+b);
                }else if (token.equals("-")) {
                    stack.push(a-b);
                }else if (token.equals("*")) {
                    stack.push(a*b);
                }else {
                    stack.push(a/b);
                }
            }
        }
        return stack.peek();
    }
    
    public static boolean isOperator(String token) {//判断是否为操作符
        return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
    }

测试代码：

public static void main(String[] args) {
            String[] cs2 = {"4","13","5","/","+"};
        value = reversePolishNotation(cs2);
        System.out.println(value);
    }

输出结果: 6