题意

给出一个只含+、-、*、左右括号和数字的表达式，求其值。

思路

给出的表达式是中缀表达式，含有括号，我们可以先将中缀表达式转为后缀表达式，再对后缀表达式直接计算，即可以算出表达式的结果。

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    stack<int> nums,oprs;
    int calc(int x,int y,int op)
    {
        if(op==1) return x+y;
        if(op==2) return y-x;
        if(op==3) return x*y;//分别表示加号减号乘号
        assert(false);//__unreachable__
    }
    int solve(string s) 
    {
        // write code here
    for(int i=0;i<s.length();i++)
    {
        if(isdigit(s[i]))
        {
            int tmpNum=s[i]-'0';
            while(isdigit(s[i+1]))
            {
                i++;
                tmpNum=tmpNum*10+s[i]-'0';//对多位数的读取
            }
            nums.push(tmpNum);
        }//如果是一个数字，将他放入数字栈
        else if(s[i]=='*') oprs.push(3);//乘号
        else if(s[i]=='(') oprs.push(4);//左括号
        else if(s[i]=='+')
        {
            while(!oprs.empty())
            {
                if(oprs.top()==4){break;}
                int a,b;
                a=nums.top();nums.pop();b=nums.top();nums.pop();
                nums.push(calc(a,b,oprs.top()));oprs.pop();
            }//因为加减的优先级小，先计算前面的式子
            oprs.push(1);//符号栈放入加号
        }
        else if(s[i]=='-')
        {
            while(!oprs.empty())
            {
                if(oprs.top()==4){break;}
                int a,b;
                a=nums.top();nums.pop();b=nums.top();nums.pop();
                nums.push(calc(a,b,oprs.top()));oprs.pop();
            }
            oprs.push(2);//同理。放入减号
        }
        else if(s[i]==')')//若读取到右括号
        {
            while(!oprs.empty())
            {
                if(oprs.top()==4){oprs.pop();break;}//直到左括号为止都不退出
                int a,b;
                a=nums.top();nums.pop();b=nums.top();nums.pop();
                nums.push(calc(a,b,oprs.top()));oprs.pop();//计算括号内表达式的值
            }
        }
    }
        while(!oprs.empty())
            {
                int a,b;if(oprs.top()==4){break;}
                a=nums.top();nums.pop();b=nums.top();nums.pop();
                nums.push(calc(a,b,oprs.top()));oprs.pop();
            }//最后计算不含括号的表达式
        return nums.top();
    }
};

复杂度分析

时间复杂度:$O(n)O(n)$,其中$n=s\mathrm{.}lengthn=s.length$，对字符串每个字符刚好读取一次。

空间复杂度:$O(n)O(n)$，只使用了存储字符串的空间。