[LeetCode] 772. Basic Calculator III

[grandyang]

 

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.

 

这道题是基本计算器系列的第三道，前两道分别为 Basic Calculator 和 Basic Calculator II，区别是，第一道只有加减法跟括号，第二道只有加减乘除法，而这第三道既有加减乘除法又有括号运算。其实做过前两道题的话，那么这道题也就没什么问题，因为把前两道题的解法综合一下就是这道题的解法啦。由于此题既有括号，又有乘除法，我们知道括号是优先级最高的，但是好就好在我们可以将括号里的内容当作一个整体调用递归函数来处理。而其他部分，就跟第二道一模一样了。我们还是分情况来处理遍历，我们需要几个变量，num 表示当前的数字，curRes 表示当前的结果，res 为最终的结果，op 为操作符号，初始化为 '+'。当遇到数字的时候，我们将 num 自乘以 10 并加上这个数字，这是由于可能遇到多位数，所以每次要乘以 10。当遇到括号的时候，这里就有一个小 trick，由于表示可能会有括号嵌套括号，所以我们如果搜索右括号的话，就有可能使得括号没有正确的匹配上，所以我们用一个变量 cnt，遇到左括号自增1，遇到右括号自减1，当 cnt 为0的时候，说明括号正好完全匹配，这个 trick 在验证括号是否 valid 的时候经常使用到。然后我们就是根据左右括号的位置提取出中间的子字符串调用递归函数，返回值赋给 num。如果遇到符号，或者是最后一个位置的字符时，我们根据 op 的值对 num 进行分别的加减乘除的处理，结果保存到 curRes 中。然后再次判读如果 op 是加或减，或者是最后一个位置的字符时，将 curRes 加到结果 res 中，并且 curRes 重置为0。最后将当前字符c赋值给 op（注意这里只有当时最后一个位置的字符时，才有可能不是运算符号，不过也不要紧了，因为遍历已经结束了），num 也要重置为0，参见代码如下：

 

class Solution {
public:
    int calculate(string s) {
        int n = s.size(), num = 0, curRes = 0, res = 0;
        char op = '+';
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                int j = i, cnt = 0;
                for (; i < n; ++i) {
                    if (s[i] == '(') ++cnt;
                    if (s[i] == ')') --cnt;
                    if (cnt == 0) break;
                }
                num = calculate(s.substr(j + 1, i - j - 1));
            }
            if (c == '+' || c == '-' || c == '*' || c == '/' || i == n - 1) {
                switch (op) {
                    case '+': curRes += num; break;
                    case '-': curRes -= num; break;
                    case '*': curRes *= num; break;
                    case '/': curRes /= num; break;
                }
                if (c == '+' || c == '-' || i == n - 1) {
                    res += curRes;
                    curRes = 0;
                }
                op = c;
                num = 0;
            }
        }
        return res;
    }
};

 

Github 同步地址：

#772

 

类似题目：

Basic Calculator IV

Basic Calculator II

Basic Calculator

 

参考资料：

https://leetcode.com/problems/basic-calculator-iii/

https://leetcode.com/problems/basic-calculator-iii/discuss/113597/C++-recursive

https://leetcode.com/problems/basic-calculator-iii/discuss/113593/C++-Consise-Solution

https://leetcode.com/problems/basic-calculator-iii/discuss/113592/Development-of-a-generic-solution-for-the-series-of-the-calculator-problems

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[JianWang2018]

题目贴错了

[grandyang]

题目贴错了

嗯嗯，已改正，多谢指出～（若发现了其他的也请指出哈）

[tangzzz-fan]

Hi, 我使用 Swift 实现了一下对应的,但是验证发现有一点问题, 我自己没有找出问题在哪里, 请帮我检查一下:

func calculate(_ expression: String) -> Int {
    var num = 0
    var sign = "+"
    var curRes = 0
    var res = 0
    let n = expression.count
    let strArr = Array(expression)
    print(expression)
    for i in 0 ..< n {
        let c = strArr[i]
        if c >= "0" && c <= "9" {            
            num = num * 10 + Int(String(c))!
        } else if c == "(" {
            let j = i
            var k = 0
            var cnt = 0
            for t in i ..< n {
                if strArr[t] == "(" {
                    cnt += 1
                }
                if strArr[t] == ")" {
                    cnt -= 1
                }
                if cnt == 0 {
                    k = t
                    break
                }
            }
            num = calculate(expression.subString(j + 1, k - i - 1))
        }
        if c == "+" || c == "-" || c == "*" || c == "/" || i == n - 1 {
            switch sign {
                case "+":
                    curRes += num
                    break
                case "-":
                    curRes -= num
                    break
                case "*":
                    curRes *= num
                    break
                case "/":
                    curRes /= num
                    break
                default:
                    break
            }
            if c == "+" || c == "-" || i == n - 1 {
                res += curRes
                curRes = 0
            }
            sign = String(c)
            num = 0
        }
    }
    return res
}

print(calculate("(45+32)"))

这一题的正确输出为 77, 但是在递归计算 45+32 时, 多算了两次, 变成了 7777.

[tangzzz-fan]

这里 for i in strArr 中 "I" 这个变量没有在出现 ")" 时 变更, 所以出现了重复计算.

[avenwu]

Java版本：

    @Test
    public void test3() {
        // "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
        assertEquals(calculate("1 + 1"),2);
        assertEquals(calculate(" 6-4 / 2 "),4);
        assertEquals(calculate("2*(5+5*2)/3+(6/2+8)"),21);
        assertEquals(calculate("(2+6* 3+5- (3*14/7+2)*5)+3"), -12);
    }

    int calculate(String exp) {
        char[] s = exp.toCharArray();
        int n = s.length, num = 0, curRes = 0, res = 0;
        char op = '+';
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                int j = i, cnt = 0;
                for (; i < n; ++i) {
                    if (s[i] == '(') ++cnt;
                    if (s[i] == ')') --cnt;
                    if (cnt == 0) break;
                }
                num = calculate(exp.substring(j + 1, i));
            }
            if (c == '+' || c == '-' || c == '*' || c == '/' || i == n - 1) {
                switch (op) {
                    case '+':
                        curRes += num;
                        break;
                    case '-':
                        curRes -= num;
                        break;
                    case '*':
                        curRes *= num;
                        break;
                    case '/':
                        curRes /= num;
                        break;
                }
                if (c == '+' || c == '-' || i == n - 1) {
                    res += curRes;
                    curRes = 0;
                }
                op = c;
                num = 0;
            }
        }
        return res;
    }

[Tanlikfeng]

想請問一下這個用c語言要怎麽寫?
"num = calculate(s.substr(j + 1, i - j - 1));"

[zch-bit]

翻译成了go lang：

func Calculator(s string) int {
	num, curRes, res := 0, 0, 0
	var op uint8 = '+'
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c >= '0' && c <= '9' {
			num = num*10 + int(c-'0')
		} else if c == '(' {
			j := i
			cnt := 0
			for ; i < len(s); i++ {
				if s[i] == '(' {
					cnt++
				}
				if s[i] == ')' {
					cnt--
				}
				if cnt == 0 {
					break
				}
			}
			num = Calculator(s[j+1 : i])
		}

		if c == '+' || c == '-' || c == '*' || c == '/' || i == len(s)-1 {
			switch op {
			case '+':
				curRes = curRes + num
			case '-':
				curRes = curRes - num
			case '*':
				curRes = curRes * num
			case '/':
				curRes = curRes / num
			}
			if c == '+' || c == '-' || i == len(s)-1 {
				res = res + curRes
				curRes = 0
			}
			op = c
			num = 0
		}
	}
	return res
}