224. Basic Calculator

Leetcode Math Stack

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 .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

分析

public static int calculator(String s) {
    int current = 0;
    char sign = '+';
    int result = 0;
    int length = s.length();
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> stackSign = new Stack<>();
    while (current < s.length()) {
        // 空格
        if (current < length && s.charAt(current) == ' ') {
            current++;
            continue;
        }
        // 处理括号
        if (s.charAt(current) == '(') {
            // find ')'
            if (sign == '+') stackSign.push(1);
            else if (sign == '-') stackSign.push(-1);
            stack.push(result);
            result = 0;
            sign = '+';
            current++;
            // 空格
            while (current < length && s.charAt(current) == ' ') current++;
        }
        // 获取数字
        int number = 0;
        while (current < length && s.charAt(current) >= '0' && s.charAt(current) <= '9') {
            number = number * 10 + s.charAt(current) - '0';
            current++;
        }
        // 符号
        if (sign == '+') {
            result += number;
        } else if (sign == '-') {
            result -= number;
        }
        if (current < length) sign = s.charAt(current);

        // 括号结束
        if (sign == ')') {
            result = result * stackSign.pop();
            result += stack.pop();
        }
        current++;
    }
    return result;
}