[leetcode] Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

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

https://oj.leetcode.com/problems/evaluate-reverse-polish-notation/

思路：stack的经典题目，遇到数字压栈，遇到符号出栈两个计算再入栈。

import java.util.Stack;

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        int a, b;
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].equals("+")) {
                a = stack.pop();
                b = stack.pop();
                stack.push(b + a);
            } else if (tokens[i].equals("-")) {
                a = stack.pop();
                b = stack.pop();
                stack.push(b - a);
            } else if (tokens[i].equals("*")) {
                a = stack.pop();
                b = stack.pop();
                stack.push(b * a);
            } else if (tokens[i].equals("/")) {
                a = stack.pop();
                b = stack.pop();
                stack.push(b / a);
            } else {
                stack.push(Integer.parseInt(tokens[i]));
            }
        }

        return stack.pop();
    }

    public static void main(String[] args) {
        System.out.println(new Solution().evalRPN(new String[] { "2", "1", "+",
                "3", "*" }));
        System.out.println(new Solution().evalRPN(new String[] { "4", "13",
                "5", "/", "+" }));
    }

}

第二遍记录：

　　注意对于减法和除法，先pop出来的被减数和被除数，后pop出来的是减数和除数。

扩展：

　　根据中序表达式生成逆波兰表示法。

第三遍记录： 实现了扩展， 中序表达式 =》逆波兰表达式，基本可以实现一个计算器的功能，支持(),+,-,*,/，并且可以扩展。

转换思路：遍历中序表达式，对于当前字符

　　如果是‘(’，直接压栈；

　　如果是')'，pop 栈内元素到输出中，直到遇到‘(’。

　　如果是0-9，直接输出。

　　如果是操作符（+-*/等），压栈之前把栈顶优先级大于等于自己的全部pop到输出 然后压栈自己。

最后将栈内剩余元素pop到输出中。

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

public class Solution {

    public int calcu(String exp) {
        return evalRPN(generateRPN(exp));
    }

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        int a, b;
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].equals("+")) {
                a = stack.pop();
                b = stack.pop();
                stack.push(b + a);
            } else if (tokens[i].equals("-")) {
                a = stack.pop();
                b = stack.pop();
                stack.push(b - a);
            } else if (tokens[i].equals("*")) {
                a = stack.pop();
                b = stack.pop();
                stack.push(b * a);
            } else if (tokens[i].equals("/")) {
                a = stack.pop();
                b = stack.pop();
                stack.push(b / a);
            } else {
                stack.push(Integer.parseInt(tokens[i]));
            }
        }

        return stack.pop();
    }

    /**
     * convert inorder expression to rerverse polish notation
     * 
     * @param inorder
     * @return
     */
    public String[] generateRPN(String inorder) {
        System.out.println("inorder:" + inorder);
        int n = inorder.length();
        Stack<Character> stack = new Stack<Character>();
        HashMap<Character, Integer> pri = new HashMap<Character, Integer>();
        config(pri);
        List<String> res = new ArrayList<String>();

        for (int i = 0; i < n; i++) {
            char ch = inorder.charAt(i);
            if (Character.isSpaceChar(ch))
                continue;

            if (ch == '(') {// for '('
                stack.push('(');
            } else if (ch == ')') { // for ')'
                char out = 0;
                while ((out = stack.pop()) != '(') {
                    res.add(out + "");
                }
            } else if (ch >= '0' && ch < '9') {// for operand
                res.add(ch + "");
            } else {// for operator
                if (stack.isEmpty() || pri.get(ch) > pri.get(stack.peek())) {
                    stack.push(ch);
                } else {
                    while (!stack.isEmpty() && pri.get(ch) <= pri.get(stack.peek())) {
                        res.add(stack.pop() + "");
                    }
                    // don't forget this
                    stack.push(ch);
                }
            }
        }
        // don't forget this
        while (!stack.isEmpty()) {
            res.add(stack.pop() + "");
        }
        String[] ret = new String[res.size()];
        res.toArray(ret);
        System.out.println("RPN:" + Arrays.toString(ret));

        return ret;
    }

    /**
     * config the priority
     * 
     * @param map
     */
    private void config(HashMap<Character, Integer> map) {
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);

        map.put('(', Integer.MIN_VALUE);

    }

    public static void main(String[] args) {
        System.out.println(new Solution().calcu("((2 + 1) * 3)"));
        System.out.println(new Solution().calcu("(4 + (3 / 5))"));
        System.out.println(new Solution().calcu("(1+2+3)"));
        System.out.println(new Solution().calcu("1+2*3+(4*5+6)*7"));
        System.out.println(new Solution().calcu("1+2*3"));
        System.out.println(new Solution().calcu("1*2+3"));
        System.out.println(new Solution().calcu("(1+2)*3"));
    }
}