题目描述：

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

题目大意：

实现一个简易计算器，计算简单表达式字符串的值。

表达式字符串只包含非负整数， +， -， *， / 运算和空白字符。整数除法的得数应当舍去小数部分。

你可以假设给定的表达式总是有效的。

测试样例见题目描述。

注意：不要使用内置的库函数eval。

解题思路：

由于表达式字符串中不包含括号，因此问题可以简化为对乘除运算与加减运算优先级的处理。

参考：https://leetcode.com/discuss/41610/ac-python-solution-use-re-to-get-the-expression

使用辅助变量d记录当前待参与运算的运算数，func记录上一个加减运算符，total记录表达式的值。

若当前运算符为乘除法，则马上对d与下一个运算数执行乘除运算，赋值给d；

若当前运算符为加减法，则对total与d执行func（加减）运算，赋值给total，并更新func；

Python代码：

class Solution:
    # @param {string} s
    # @return {integer}
    def calculate(self, s):
        s = re.sub(r'\d+', ' \g<0> ', s)
        op = {'+': operator.add, '-': operator.sub,
              '*': operator.mul, '/': operator.floordiv}
        expression = s.split()
        total = d = idx = 0
        func = op['+']
        while idx < len(expression):
            e = expression[idx]
            if e in '+-':
                total = func(total, d)
                func = op[e]
            elif e in '*/':
                idx += 1
                d = op[e](d, int(expression[idx]))
            else:
                d = int(e)
            idx += 1
        return func(total, d)

另外，在LeetCode Discuss还看到一段非常简洁的C++代码，思路同上。

C++代码：

class Solution {
public:
    int calculate(string s) {
        istringstream in(s + "+");
        long long total = 0, term, sign = 1, n;
        in >> term;
        char op;
        while (in >> op) {
            if (op == '+' || op == '-') {
                total += sign * term;
                sign = 44 - op; //op == '+' ? 1 : -1
                in >> term;
            } else {
                in >> n;
                if (op == '*')
                    term *= n;
                else
                    term /= n;
            }
        }
        return total;
    }
};

 

本文链接：http://bookshadow.com/weblog/2015/06/23/leetcode-basic-calculator-ii/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码