Leetcode 227 basic caculator

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

分析：题目主要的难点在于*，/比+，-有更高的优先级，所以，当处理到低优先级的+,-时，不能直接计算，而要等看后面的操作符，可以分为两种情况：

1. 如果后续的操作符是相同优先级，则要先计算前面操作符；

2. 如果后续的是高优先级的操作符，则要先计算后续的操作符；

处理好这两种情况，就可以完成了；

public class Solution {

    public static void main(String[] args) {
        System.out.println("3+2*2 = " + calculate("3+2*2"));
        System.out.println(" 3/2  = " + calculate(" 3/2 "));
        System.out.println(" 3+5 / 2  = " + calculate(" 3+5 / 2 "));
    }

    public static int calculate(String s) {
        char[] cs = s.toCharArray();

        Stack stack = new Stack();
        for (int i = 0; i < cs.length; ) {
            if (cs[i] == ‘ ‘) {
                i++;
                continue;
            }

            if (isMul(cs[i]) || isAdd(cs[i])) {
                stack.addOp(cs[i]);
                i++;
                continue;
            }
            int num = 0;
            while (i < cs.length && isNum(cs[i])) {
                num = num * 10 + (cs[i] - ‘0‘);
                i++;
            }
            stack.addNum(num);
        }

        return stack.eval();
    }

    static boolean isNum(char c) {
        return c >= ‘0‘ && c <= ‘9‘;
    }

    static boolean isMul(char c) {
        return c == ‘*‘ || c == ‘/‘;
    }

    static boolean isAdd(char c) {
        return c == ‘+‘ || c == ‘-‘;
    }

    static class Stack {
        int[] nums = new int[3];
        int pnum = -1;
        char[] ops = new char[2];
        int pop = -1;

        public void addOp(char op) {
            if (isAdd(op) && pop == 0) {
                int b = nums[pnum--];
                int a = nums[pnum--];
                int c = calc(a, b, ops[pop--]);
                nums[++pnum] = c;
            }
            ops[++pop] = op;
        }

        public void addNum(int num) {
            nums[++pnum] = num;
            if (pop >= 0 && isMul(ops[pop])) {
                int b = nums[pnum--];
                int a = nums[pnum--];
                int c = calc(a, b, ops[pop--]);
                nums[++pnum] = c;
            }
        }

        int calc(int a, int b, char op) {
            int c = 0;
            switch (op) {
                case ‘+‘:
                    c = a + b;
                    break;
                case ‘-‘:
                    c = a - b;
                    break;
                case ‘*‘:
                    c = a * b;
                    break;
                case ‘/‘:
                    c = a / b;
                    break;
                default:
                    throw new IllegalArgumentException("unknown operator " + c);
            }
            return c;
        }

        public int eval() {
            if (pnum == 0) {
                return nums[pnum--];
            } else {
                int b = nums[pnum--];
                int a = nums[pnum--];
                char c = ops[pop--];
                return calc(a, b, c);
            }
        }
    }
}

这里模拟了一个Stack，

1. 以处理1 + 2 * 3为例，在加入2的时候，不能计算1 + 2， 因为不知道后续操作符的优先级；等加入*的时候，可以确定当前的优先级肯定比前面的大，（在stack里面至多存在一个*或者/）；当加入3的时候，发现前面是一个高优先级的*，可以直接计算，得到6，并把结果放到栈顶。继续处理后续的输入；

2. 以处理1 + 2 - 3为例，在输入-号之前，和前面的处理是一样的；判断是低优先级的，并且栈底有输入，将栈底的先计算出来，得到3，重新压入栈底（不要忘记了），然后加入新的-；然后加入3；

所以，可以看到，栈里面最多只有4个元素，2个操作数，和2个操作符；

时间复杂度是O(n), 空间复杂度是O(1)；

Leetcode 227 basic caculator

原文：http://my.oschina.net/u/922297/blog/469449