LeetCode 第772题 Basic Calculator III 简要分析及Python代码

Title: LeetCode Problem 772. Basic Calculator III 简要分析及Python代码

Date: 2018-01-24

Category: Programming

Tags: LeetCode, Python, Programming, Solution, Hard, Algorithm

Slug: leetcode-765

Author: ouankou

LeetCode 第772题 Basic Calculator III 简要分析及Python代码

题目：

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 .

Examples:

Note:

Do not use the built-in library function.

难度:

Hard.

分析:

本答案利用函数递归调用来解题，该方法较易于理解，但消耗内存大，速度慢。另可使用堆（stack）方法解题，更为有效率，会另开新文分析。

首先将原始算式的字符串拆解为单个元素的全局列表，去除空格，只保留操作数、括号、运算符。如变为。

然后将操作范围的起始位置作为参数传给子函数来获取该范围的运算结果。对给定的范围从后向前进行运算符查找，首先查找加减号，遍历一次后如果未发现就从后向前再次遍历寻找乘除号。如果这两次遍历中发现任何运算符，立即对运算符两侧部分各自调用获取该部分结果。例如发现了乘号，则对乘号两侧部分调用，然后将两个结果做乘法。

因为四则运算的优先级，乘除优先于加减，左优先于右。我们从后向前查找，先找加减号，后找乘除号。这是因为先调用的函数要等待后调用函数的结果才能继续运算，所以优先度最高的运算会最后被调用，最先得到结果并返回给优先度低的运算。

另一个重要的问题是处理括号。成对括号之间的部分可以理解为一个不可与括号外混合的子算式，也就是说每对括号间的部分都要作为一个整体交给处理。

因为当发现时，要确保跳过它所对应的后再查找运算符进一步拆分处理。

这里涉及另一个问题是如何识别处理括号内的部分。刚才说过跳过成对括号找运算符，那么如果所计算的部分就是整个括号部分呢？因此在两次遍历后，如果没有任何进一步拆分处理，说明没有独立的运算符存在。那么该部分要么只是一个操作数，例如，这种情况只需直接将这部分字符串转换为整数并返回即可；要么这部分起始两端就是一对括号，这种情况下只需跳过这两个字符，调用处理中间的部分。例如遇到，调用处理中间的。

需要注意的是对于第二种情况的判断，必须在遍历运算符后进行，因为并不是其实两端是成对括号就代表这是一个整体，例如，这是两对括号和一个减法运算符，不能拆分处理中间的部分。

函数递归调用的终点在上面已经提到，就是当所分析的部分没有括号，没有运算符，只剩下数字时。此时将字符串转换为整数返回。这样一层层返回局部结果，直到得到最终的完整运算结果。

例子1:

输入为。按照上述算法分析，首先去掉空格并拆分元素，得到列表遇到后对左右两侧分别计算。左侧显然为单个操作数。右侧为，可进一步在处拆分左右两侧得到和。然后按照调用次序逆向返回计算结果。

即首先得到返回，然后得到，即为最终运算结果。

例子2:

输入为。得到元素列表后开始遍历，首先遇到括号，记录目前遇到的右括号数量为。当发现配对的左括号后，将计数减1得到，意味着已完整跳过当前经历的所有成对括号，可以继续查找运算符号并拆分处理了。然后遇到，则对左侧和右侧分别处理。右侧为一成对括号，则去除括号对进行计算，最终得到。左侧同理，第一次遍历时未发现加减号，括号部分整体被跳过不计。然后遍历乘除号，先遇到，则拆分为和。依照上述算法，左侧最终得到结果。算式转化为，得到最终完整结果。

完整Python代码：