772.Basic-Calculator-III

772. Basic Calculator III

题目地址

https://leetcode.com/problems/basic-calculator-iii/

题目描述

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

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

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

Some examples:

"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

代码

Approach 1: Queue + Stack，遇到下一个sign时，再计算之前sign

• Queue: 存储所有的字符

• Stack 存储所有的num

class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) return 0;
        Queue<Character> q = new LinkedList<>();
        for (char c : s.toCharArray()) {
            q.offer(c);
        }
        q.offer('+');
        return cal(q);
    }

    private int cal(Queue<Character> q) {
        char sign = '+';
        Integer num = null;     // 1 - 0 - 1
        Stack<Integer> stack = new Stack<>();
        while (!q.isEmpty()) {
            char c = q.poll();
            if (c == ' ') continue;
            if (Character.isDigit(c)) {
                if (num != null) {
                    num = 10 * num + c - '0';
                } else {
                    num = c - '0';
                }
            } else if (c == '(') {
                num = cal(q);
            } else {
        // + - * / )
                if (sign == '+' && num != null) {
                    stack.push(num);
                } else if (sign == '-') {
                    if (c == '-' && num == null) { // -1--1
                        c = '+'; // Negative + negative to positive
                    } else if(num != null){
                        stack.push(-num);
                    }
                } else if (sign == '*' && num != null) {
                    stack.push(stack.pop() * num);
                } else if (sign == '/' && num != null) {
                    stack.push(stack.pop() / num);
                }

                if (c == ')') {
                    break;
                }
                num = null;
                sign = c;
            }
        }

        int sum = 0;
        while (!stack.isEmpty()) {
            sum += stack.pop();
        }
        return sum;
    }

}