题意分析

• 给出一个合法的表达式，需要我们计算这个表达式的值。

思路分析

• 对于这种表达式的求值，我们在确实输入的序列是合法的情况下我们可以使用递归的方法进行求解。我们可以递归计算每个括号的值，然后我们将整个表达式切分成数值和运算符的形式，我们将我们得到的数值放到栈里面，然后将所有的符号都尽量转化为加法的操作，比如减法的话就取个反，乘法的话就先计算出来。

• 我们重点来讲一个如何对一个序列进行切分，这里我们需要把一个括号里面的计算的值看作是一个数字，因为我们最后肯定是可以将这个表达式计算出来的。即使有括号的嵌套也是这样的，我们进行递归操作。这样下来，我们的表达式就变成了只有数值和运算符两部分组成的了。

• 样例2更具有典型性，所以我们对其进行图解，样例2解释如下

解法一 C++递归写法

• 代码如下
  • 我们需要遍历整个字符序列，即使存在递归，遍历的次数也是1，所以总的时间复杂度为$O(n)O(n)$
  • 过程中我们利用了栈来存储序列的数值，空间复杂度为$O(n)O(n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        stack<int> val;
        int sum=0;
        char flag='+'; // 用来记录某一个表达式前面的符号是什么
        for(int i=0;i<=s.size();i++){
            if(s[i]>='0'&&s[i]<='9'){
                sum=10*sum+s[i]-'0';
            }
            if(s[i]=='('){
                int j=i+1;
                int cnt=1; // 这里用一个数字来标记，要求出现的括号呈对数出现
                while(cnt){
                    if(s[j]=='(') cnt++;
                    if(s[j]==')') cnt--;
                    j++;
                }
                // 进行递归求这个括号内的序列的值
                sum=solve(s.substr(i+1,j-1-i));
                i=j;
            }
            if(i==s.size()||s[i]=='+'||s[i]=='-'||s[i]=='*'){
                // 判断这个表达式的符号进行相应的处理
                if(flag=='+'){
                    val.push(sum);
                }
                if(flag=='-'){
                    val.push(-sum);
                }
                if(flag=='*'){
                    sum=sum*val.top();
                    val.pop();
                    val.push(sum);
                }
                flag=s[i];
                sum=0;
            }
        }
        
        int ans=0;
        while(!val.empty()){
            ans+=val.top();
            val.pop();
        }
        
        return ans;
    }
};

解法二 Python

• 这个作为扩宽见识，当作学习不推荐使用。

• 代码如下

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
class Solution:
    def solve(self , s ):
        # write code here
        return eval(s)