150. Evaluate Reverse Polish Notation

简单又经典的一道题，注意一下string和int的类型就行了。

这道逆波兰表达式里，每一个数字都是string存在字符串数组里面，也就是说一个multiple digits的数字也不用特殊处理，但不是每道题都能这么方便，遇到char需要手动加空格（padding）处理。

06/16更新：Integer.parseInt(str) 熟悉接口很重要啊，不然要自己写，还容易出错。转换int的时候都忘了考虑负数了。

public class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) return -1;
        Stack<Integer> stack = new Stack<>();

        for (String str : tokens) {
            if (str.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (str.equals("-")) {
                int sec = stack.pop();
                int fir = stack.pop();
                stack.push(fir - sec);
            } else if (str.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (str.equals("/")) {
                int sec = stack.pop();
                int fir = stack.pop();
                stack.push(fir / sec);
            } else {
                stack.push(Integer.parseInt(str));
            }
        }
        return stack.pop();
    }
}

224. Basic Calculator

计算器类问题，离不开 Dijkstra 的 Shunting-yard algorithm 和 reverse polish notation.

Input: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

  • 因为有负号，运算顺序不能颠倒；

  • 数字可能是多数位的，也可能是0，不能 assume 都是一位数；

  • 带括号的处理方式；

复现了一下 Dijkstra 的 shunting yard algorithm，因为只有 “+” 和 “-” ，运算符优先级上要简单一些。在这个代码基础上扩展任何新的运算符都很容易，加个判断函数就行了。

  • 建个 StringBuilder 存输出的 RPN，一个 Stack 存运算符；

  • 如果看到数字，直接添加到 StringBuilder 中；

  • 如果看到 "(" ，直接添加到 Stack 上；

  • 如果看到 ")"，把 Stack 上的所有运算符 pop 出来添加到 StringBuilder，直到遇见 "(" 为止；

  • （本题用不上）如果看到运算符，把 Stack 上所有 "大于等于当前运算符优先级" 的 pop 出来加到 StringBuilder，最后把自己放入 Stack，此时要么 Stack 为空，要么 Stack.peek() 的优先级比当前运算符小。

  • 优先级 ："乘除 = 3"， "加减 = 2”

这道题的核心就是怎么把一个数学表达式转换成逆波兰表达式，最后再用逆波兰计算。

关键是multiple digits，带空格，有零，这些corner case，转换成char再转换string之间的处理。并不难，但要写出bug free需要一定的练习。

06/19更新：这道题和LC71有一个细节是一样的，就是对于空字符串的处理，很显然你要考虑跳过空字符串，不然会出错，但我觉得这个细节很神奇在于这些空字符串是怎么来的呢？

public class Solution {
    public int calculate(String s) {
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);

            if (ch == ' ') continue;
            if (Character.isDigit(ch)) {
                sb.append(ch);
            } else {
                sb.append(' ');
                if (ch == '(') {
                    stack.push(ch);
                } else if (ch == ')') {
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        sb.append(stack.pop());
                        sb.append(' ');
                    }
                    stack.pop();
                } else {
                    while(!stack.isEmpty() && stack.peek() != '('){
                        sb.append(stack.pop());
                        sb.append(' ');
                    } 
                    stack.push(ch);
                }
            }
        }
        while(!stack.isEmpty()) {
            sb.append(' ');
            sb.append(stack.pop());
        }

        return rePolish(sb.toString());
    }

    private int rePolish(String s){
        String[] strs = s.split(" ");
        Stack<Integer> stack = new Stack<>();
        for(String str : strs){
            if(str.equals("")) continue;
            if("+-".indexOf(str) != -1){
                int num2 = stack.pop();
                int num1 = stack.pop();

                if(str.equals("+")) stack.push(num1 + num2);
                if(str.equals("-")) stack.push(num1 - num2);
            } else {
                stack.push(Integer.parseInt(str));
            }
        }

        return stack.pop();
    }
}

227. Basic Calculator II

思路是一样的，两点注意：

  • char类型要用==和!=，string要用.equal()，总忘。

  • 最后stack清空的时候，padding在前，sb.append(' ')在pop之前。

public class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) return 0;
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);

            if (ch == ' ') continue;
            if (Character.isDigit(ch)) {
                sb.append(ch);
            } else {
                sb.append(' ');
                if (ch == '(') {
                    stack.push(ch);
                } else if (ch == ')') {
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        sb.append(stack.pop());
                        sb.append(' ');
                    }
                    stack.pop();
                } else {
                    while (!stack.isEmpty() && getPrecedence(ch) <= getPrecedence(stack.peek())) {
                        sb.append(stack.pop());
                        sb.append(' ');
                    }
                    stack.push(ch);
                }
            }
        }
        while (!stack.isEmpty()) {
            sb.append(' ');
            sb.append(stack.pop());
        }
        return rePolish(sb.toString());
    }
    private int rePolish(String s) {
        String[] strs = s.split(" ");
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < strs.length; ++i) {
            String str = strs[i];
            if (str.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (str.equals("-")) {
                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(num1 - num2);
            } else if (str.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (str.equals("/")) { 
                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(num1 / num2);
            } else {
                stack.push(Integer.parseInt(str));
            }
        }
        return stack.pop();
    }
    private int getPrecedence(char ch) {
        if (ch == '*' || ch == '/') return 3;
        if (ch == '+' || ch == '-') return 2;
        return 0;
    }
}

439. Ternary Expression Parser

根据规则，得从后面先判断。因为数字只有一位，所以pop出来的必定是符号"?"，第一个数，符号":"，第二个数。再根据前面的tf push进结果。

public String parseTernary(String expression) {
    if (expression == null || expression.length() == 0) return "";
    Deque<Character> stack = new LinkedList<>();

    for (int i = expression.length() - 1; i >= 0; i--) {
        char c = expression.charAt(i);
        if (!stack.isEmpty() && stack.peek() == '?') {

            stack.pop(); //pop '?'
            char first = stack.pop();
            stack.pop(); //pop ':'
            char second = stack.pop();

            if (c == 'T') stack.push(first);
            else stack.push(second);
        } else {
            stack.push(c);
        }
    }

    return String.valueOf(stack.peek());
}

results matching ""

    No results matching ""