题目
给你一个字符串表达式 s
,请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如
eval()
。
示例 1:
示例 2:
示例 3:
1 2
| 输入:s = "(1+(4+5+2)-3)+(6+8)" 输出:23
|
提示:
1 <= s.length <= 3 * 105
s
由数字、'+'
、'-'
、'('
、')'
、和
' '
组成
s
表示一个有效的表达式
- '+' 不能用作一元运算(例如, "+1" 和
"+(2 + 3)"
无效)
- '-' 可以用作一元运算(即 "-1" 和
"-(2 + 3)"
是有效的)
- 输入中不存在两个连续的操作符
- 每个数字和运行的计算将适合于一个有符号的 32位 整数
题解
这道题的坑老多了,首先,-可以是负号也可以是运算符,个人感觉全当作负号,然后默认添加一个加号比较好处理;
其次是数字有多个位;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| class Solution { public int calculate(String s) { Deque<Integer> nums = new ArrayDeque<>(); nums.addLast(0); s = s.replaceAll(" ", ""); Deque<Character> ops = new ArrayDeque<>(); int n = s.length(); char[] cs = s.toCharArray(); for (int i = 0; i < n; i++) { char c = cs[i]; if (c == '(') { ops.addLast(c); } else if (c == ')') { while (!ops.isEmpty()) { char op = ops.peekLast(); if (op != '(') { calc(nums, ops); } else { ops.pollLast(); break; } } } else { if (isNum(c)) { int u = 0; int j = i; while (j < n && isNum(cs[j])) u = u * 10 + (int)(cs[j++] - '0'); nums.addLast(u); i = j - 1; } else { if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) { nums.addLast(0); } while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops); ops.addLast(c); } } } while (!ops.isEmpty()) calc(nums, ops); return nums.peekLast(); } void calc(Deque<Integer> nums, Deque<Character> ops) { if (nums.isEmpty() || nums.size() < 2) return; if (ops.isEmpty()) return; int b = nums.pollLast(), a = nums.pollLast(); char op = ops.pollLast(); nums.addLast(op == '+' ? a + b : a - b); } boolean isNum(char c) { return Character.isDigit(c); } }
|