[LeetCode] 772. Basic Calculator III

Implement a basic calculator to evaluate a simple expression string.

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].

Follow up: Could you solve the problem without using built-in library functions.

Example 1:

Input: s = "1 + 1"
Output: 2
Example 2:

Input: s = " 6-4 / 2 "
Output: 4
Example 3:

Input: s = "2*(5+5*2)/3+(6/2+8)"
Output: 21
Example 4:

Input: s = "(2+6* 3+5- (3*14/7+2)*5)+3"
Output: -12
Example 5:

Input: s = "0"
Output: 0

Constraints:

1 <= s <= 104
s consists of digits, '+', '-', '*', '/', '(', ')' and ' '.
s is a valid expression.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/basic-calculator-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

基本计算器 III。

题意是前两个版本的综合，既要处理四则运算，又要处理带括号的情形。

思路是递归 + 栈。我参考了这个帖子。为什么要用栈，是为了在遇到符号的时候，你要计算局部结果；为什么要用递归，是因为你不知道到底有多少层括号的嵌套，而且因着有乘除法的关系，我们必须先计算好括号内的内容，才能把括号内的局部结果拿出来参与别的运算。这里我们一开始需要一个全局变量index来帮助track到底走到input字符串的什么位置上了。然后我们开始遍历input，这里我们还是像前两个版本一样创建两个变量，sign表示符号，num表示遇到的数字，这里都很正常。当遇到一个左括号的时候，括号内的局部结果 num 就需要用递归来计算了。

时间O(n!) - worst case

空间O(n)

Java实现

class Solution {
    private int index = 0;

    public int calculate(String s) {
        char[] ch = s.toCharArray();
        return cal(ch);
    }

    private int cal(char[] ch) {
        Deque<Integer> stack = new ArrayDeque<>();
        int num = 0;
        char sign = '+';
        while (index < ch.length) {
            char c = ch[index];
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }
            if (c == '(') {
                index++; // index指针指到下一个字符
                num = cal(ch);
            }

            // 当遇到了新的运算符，就要对上一个运算符sign和累计的数字num作运算
            // 空格直接无视，i继续前进
            // 遇到字符串末尾，肯定是要结算的
            if (!Character.isDigit(c) && c != ' ' || index == ch.length - 1) {
                // int pre = 0;
                if (sign == '+') {
                    stack.push(num);
                } else if (sign == '-') {
                    stack.push(-num);
                } else if (sign == '*') {
                    stack.push(stack.pop() * num);
                } else if (sign == '/') {
                    stack.push(stack.pop() / num);
                }
                sign = c;
                num = 0;
            }
            if (c == ')') {
                break; //阶段，后面开始计算局部结果，返回
            }
            index++;
        }

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

相关题目

224. Basic Calculator

227. Basic Calculator II

772. Basic Calculator III

LeetCode 题目总结