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
Note: Do not use the
eval
built-in library function.当处理到括号的时候用递归
1. I,II和III的通解都可以是:把加减号和值,乘除号和值分别预存起来。
2. 遇到数字计算乘除的值
3.遇到加减号说明乘除已经定下,计算加减号的值
ref:http://shibaili.blogspot.com/2018/08/772-basic-calculator-iii.html
ToDo: 把I,II用类似方法再写一次
class Solution { public int calculate(String s) { int op1 = 1, op2 = 1; int val1 = 0, val2 = 1; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (Character.isDigit(c)) { int num = c - '0'; while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) { num = num * 10 + (s.charAt(i + 1) - '0'); i++; } val2 = op2 == 1 ? val2 * num : val2 / num; }else if (c == '(') { int cur = i; int count = 0; while (i < s.length()) { char ch = s.charAt(i); if (ch == '(') count++; if (ch == ')') count--; if (count == 0) break; i++; } int num = calculate(s.substring(cur + 1,i)); val2 = op2 == 1 ? val2 * num : val2 / num; }else if (c == '+' || c == '-') { val1 = val1 + op1 * val2; op1 = c == '+' ? 1 : -1; op2 = 1; val2 = 1; }else if (c == '*' || c == '/') { op2 = c == '*' ? 1 : -1; } } return val1 + op1 * val2; } }
楼主,这个code没ac啊
ReplyDelete