题解 | #表达式求值#

题目的主要信息：

• 写一个支持+ - *三种符号的运算器，其中优先级+ - 是一级，*更高一级
• 支持括号运算

举一反三：

BM44. 有效括号序列

方法：栈 + 递归（推荐使用）

知识点：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：

对于上述两个要求，我们要考虑的是两点，一是处理运算优先级的问题，二是处理括号的问题。

处理优先级问题，那必定是乘号有着优先运算的权利，加号减号先一边看，我们甚至可以把减号看成加一个数的相反数，则这里只有乘法和加法，那我们优先处理乘法，遇到乘法，把前一个数和后一个数乘起来，遇到加法就把这些数字都暂时存起来，最后乘法处理完了，就剩余加法，把之前存起来的数字都相加就好了。

处理括号的问题，我们可以将括号中的部分看成一个新的表达式，即一个子问题，因此可以将新的表达式递归地求解，得到一个数字，再运算：

• 终止条件： 每次遇到左括号意味着进入括号子问题进行计算，那么遇到右括号代表这个递归结束。
• 返回值： 将括号内部的计算结果值返回。
• 本级任务： 遍历括号里面的字符，进行计算。

具体做法：

• step 1：使用栈辅助处理优先级，默认符号为加号。
• step 2：遍历字符串，遇到数字，则将连续的数字字符部分转化为int型数字。
• step 3：遇到左括号，则将括号后的部分送入递归，处理子问题；遇到右括号代表已经到了这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。
• step 4：当遇到符号的时候如果是+，得到的数字正常入栈，如果是-，则将其相反数入栈，如果是*，则将栈中内容弹出与后一个元素相乘再入栈。
• step 5：最后将栈中剩余的所有元素，进行一次全部相加。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public ArrayList<Integer> function(String s, int index){
        Stack<Integer> stack = new Stack<Integer>(); 
        int num = 0;
        char op = '+';
        int i;
        for(i = index; i < s.length(); i++){
            //数字转换成int数字
            //判断是否为数字
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){ 
                num = num * 10 + s.charAt(i) - '0';
                if(i != s.length() - 1)
                    continue;
            }
            //碰到'('时，把整个括号内的当成一个数字处理
            if(s.charAt(i) == '('){
                //递归处理括号
                ArrayList<Integer> res = function(s, i + 1);
                num = res.get(0);
                i = res.get(1);
                if(i != s.length() - 1)
                    continue;
            }            
            switch(op){
            //加减号先入栈
            case '+': 
                stack.push(num);
                break;
            case '-':
                //相反数
                stack.push(-num);
                break;
            //优先计算乘号
            case '*':  
                int temp = stack.pop();
                stack.push(temp * num);
                break;
            }
            num = 0;
            //右括号结束递归
            if(s.charAt(i) == ')') 
                break; 
            else 
                op = s.charAt(i);
        }
        int sum = 0;
        //栈中元素相加
        while(!stack.isEmpty())  
            sum += stack.pop();
        ArrayList<Integer> temp = new ArrayList<Integer>();
        temp.add(sum);
        temp.add(i);
        return temp; 
    }
    public int solve (String s) {
        ArrayList<Integer> res = function(s, 0);
        return res.get(0);
    }
}

C++实现代码：

class Solution {
public:
    vector<int> function(string s, int index){
        stack<int> stack; 
        int num = 0;
        char op = '+';
        int i;
        for(i = index; i < s.length(); i++){
            //数字转换成int数字
            if(isdigit(s[i])){
                num = num * 10 + s[i] - '0';
                if(i != s.length() - 1)
                    continue;
            }
            //碰到'('时，把整个括号内的当成一个数字处理
            if(s[i] == '('){
                //递归处理括号
                vector<int> res = function(s, i + 1);
                num = res[0];
                i = res[1];
                if(i != s.length() - 1)
                    continue;
            }           
            switch(op){
            //加减号先入栈
            case '+': 
                stack.push(num);
                break;
            case '-':
                //相反数
                stack.push(-num);
                break;
            //优先计算乘号
            case '*':  
                int temp = stack.top();
                stack.pop();
                stack.push(temp * num);
                break;
            }
            num = 0;
            //右括号结束递归
            if(s[i] == ')')
                break; 
            else 
                op = s[i];
        }
        int sum = 0;
        //栈中元素相加
        while(!stack.empty()){  
            sum += stack.top();
            stack.pop();
        }
        return vector<int> {sum, i}; 
    }
    
    int solve(string s) {
        return function(s, 0)[0];
    }
};

Python代码实现：

class Solution:
    def solve(self , s ):
        s = s.strip()
        stack = []
        res = 0
        num = 0
        sign = '+' 
        index = 0
        while index < len(s):
            if s[index] == ' ':
                index += 1
                continue
            # 遇到左括号
            if s[index] == '(': 
                end = index + 1
                lens = 1
                while lens > 0: 
                    if s[end] == '(':
                        lens += 1
                    if s[end] == ')':
                        lens -= 1
                    end += 1
                #将括号视为子问题进入递归
                num = self.solve(s[index + 1: end - 1]) 
                index = end - 1
                continue
            #字符数字转换成int数字
            if '0' <= s[index] <= '9':
                num = num * 10 + int(s[index])
            #根据符号运算
            if not '0' <= s[index] <= '9' or index == len(s) - 1:
                #加
                if sign == '+': 
                    stack.append(num)
                #减，加相反数
                elif sign == '-': 
                    stack.append(-1 * num)
                #乘优先计算
                elif sign == '*': 
                    stack.append(stack.pop() * num) 
                num = 0
                sign = s[index]
            index += 1
        #栈中元素相加
        while stack: 
            res += stack.pop()
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，$nn$为字符串长度，相当于遍历一遍字符串全部元素
• 空间复杂度：$O(n)O(n)$，辅助栈和递归栈的空间