224. 基本计算器

题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

• 1 <= s.length <= 3 * 105
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式

思路分析

​ 这道题目只考虑加减符号还有括号，不需要考虑乘除的优先级，可以把括号去掉再进行运算。例如1-((2+3)-(4-5))去掉括号后编程1-2-3+4-5，仔细体会这个过程，可以看到关键点在于去掉括号的时候加减号的变化。

​ 为了解决上面提出的问题，括号是一层层囊括的，和栈结构很类似，可以考虑使用栈来保存当前数字的符号，栈顶表示在当前括号内的符号。设定一个全局的符号表示sign，初始sign=1，表示是＋，并压入栈内，如果遇到+号，表示符号不变，sign=栈顶，如果遇到-号，符号需要反转，sign=-栈顶。如果遇到（，表示进入一层新的循环，那么把该循环的符号sign入栈，如果遇到)，表示出来了一层循环，那么出栈。如果遇到数字，把字符串转化为数字，根据sign的取值巨顶正负。

代码实现

class Solution {
public:
    int calculate(string s) {
        int len=s.size();
        int sign=1; //全局符号标识符
        stack<int>op; //符号栈
        op.push(1);  //初始默认是+
        int res=0;   //结果值
        for(int i=0;i<len;i++)
        {
            //遇到空字符跳过
            if(s[i]==' ')
                continue;
            //遇到正号不反转
            else if(s[i]=='+')
                sign=op.top();  
            //遇到符号反转
            else if(s[i]=='-')
                sign=-op.top();
            //遇到（入栈
            else if(s[i]=='(')
            {
                op.push(sign);
                sign=op.top();
            }
            //遇到）出栈
            else if(s[i]==')')
            {
                op.pop();   
                sign=op.top(); 
            }

            else
            {
                //把字符串转为数字
                int num=0;
                while(i<len&&s[i]>='0'&&s[i]<='9')
                {
                    num=num*10-'0'+s[i];
                    i++;
                }
                i--;  //此处减去一，是为了防止循环中的i++跳过字符
                //根据符号决定加减
                res+=sign*num;
            }         
        }
        return res;
    }

};