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实现
1 class Solution {
2 private int index;
3
4 public int calculate(String s) {
5 char[] ch = s.toCharArray();
6 return cal(ch);
7 }
8
9 private int cal(char[] ch) {
10 Deque<Integer> stack = new ArrayDeque<>();
11 int num = 0;
12 char sign = '+';
13 for (index = 0; index < ch.length; index++) {
14 char c = ch[index];
15 if (Character.isDigit(c)) {
16 num = num * 10 + (c - '0');
17 }
18 if (c == '(') {
19 index++; // index指针指到下一个字符
20 num = cal(ch);
21 }
22
23 // 当遇到了新的运算符，就要对上一个运算符sign和累计的数字num作运算
24 // 空格直接无视，i继续前进
25 // 遇到字符串末尾，肯定是要结算的
26 if (!Character.isDigit(c) && c != ' ' || index == ch.length - 1) {
27 int pre = 0;
28 switch (sign) {
29 case '+':
30 stack.push(num);
31 break;
32 case '-':
33 stack.push(-num);
34 break;
35 case '*':
36 pre = stack.pop();
37 stack.push(pre * num);
38 break;
39 case '/':
40 pre = stack.pop();
41 stack.push(pre / num);
42 break;
43 }
44 sign = c;
45 num = 0;//计数归位
46 }
47 if (c == ')') {
48 break; //阶段，后面开始计算局部结果，返回
49 }
50 }
51
52 int res = 0;
53 while (!stack.isEmpty()) {
54 res += stack.pop();
55 }
56 return res;
57 }
58 }
相关题目