【编程】逆波兰表达式求值

逆波兰表达式求值

描述

求逆波兰表达式的值。
在逆波兰表达法中，其有效的运算符号包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰计数表达。

样例

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

考察点

• 先进后出
  • Stack

答案

public int evalRPN(String[] tokens) {
    Stack<String> mStack = new Stack<>();
    for (int i = 0; i < tokens.length; i++) {
        String str = tokens[i];
        int num1, num2 = 0;
        switch (isNum(str)) {
            case 0:
                mStack.push(str);
                break;
            case 1:
                num1 = Integer.valueOf(mStack.pop());
                num2 = Integer.valueOf(mStack.pop());
                mStack.push(num2 + num1 + "");
                break;
            case 2:
                num1 = Integer.valueOf(mStack.pop());
                num2 = Integer.valueOf(mStack.pop());
                mStack.push(num2 - num1 + "");
                break;
            case 3:
                num1 = Integer.valueOf(mStack.pop());
                num2 = Integer.valueOf(mStack.pop());
                mStack.push(num2 * num1 + "");
                break;
            case 4:
                num1 = Integer.valueOf(mStack.pop());
                num2 = Integer.valueOf(mStack.pop());
                mStack.push(num2 / num1 + "");
                break;
        }
    }
    return Integer.valueOf(mStack.pop());
}


public int isNum(String str) {
    if (str.equals("+")) {
        return 1;
    } else if (str.equals("-")) {
        return 2;
    } else if (str.equals("*")) {
        return 3;
    } else if (str.equals("/")) {
        return 4;
    }
    return 0;
}