Tuesday, August 21, 2018

772. Basic Calculator III

772Basic Calculator III
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;
    }
}

1 comment: