LeetCode-Basic Calculator题解

1.题目描述：

题目大意是实现一个只有加法，减法和括号的表达式求值，表达式中所有数都是正整数。

2.解题思路：

这道题其实是一道简化版的表达式求值问题，可以使用经典的算符优先法求解，即建立运算符栈和操作数栈，然后进行各种进出栈操作。同时这道题只有加号，减号和括号三种运算符的特性有让我们对算符优先法进行一些简化。

首先体现在算符优先关系的简化上，算符优先关系可以概括为右括号大于加减号大于左括号，同时后入的加减号优先级大于之前的加减号。这种比较简便的运算符优先级关系使我们可以不用二阶矩阵或专门写个Precede函数来储存优先关系。注意到‘)'因为优先级最大永远不会进栈，我们可以将'('在运算符栈中存储为0，将'+'存储为1，'-'存储为-1。这种简化的好处是减少了代码量，在加减法运算时代码显得更简洁。

另外为了让运算符栈里总有东西，以免总要判断栈是不是空的或者引发未知bug，我们把待求值表达式整体用一对小括号括上，这样不会改变表达式的值，也省去了不少麻烦。

3.具体代码：

这道题的整体思路是算符优先法，具体的一些算法思路的解释体现在下面这段代码的注释上，下面的代码实在LeetCode平台上提交的代码。

class Solution {
public:
    int calculate(string s) {
        s = s + ")";
        stack<int> optr;
        stack<int> opnd;
        optr.push(0);
        int temp1 = 0;
        int temp2 = 0;
        int temp  = 0;
        for(int i = 0; i < s.length(); i++)
        {
            if(s[i] <= '9' && s[i] >= '0')          //操作数进操作数栈
            {
                temp = s[i] - '0';
                while(i != (s.length() - 1) && s[i+1] <= '9' && s[i+1] >= '0' ) //处理多位数的情况
                {
                    i++;
                    temp = temp * 10 + s[i] - '0';
                }
                opnd.push(temp);
            }
            else
            {
                switch(s[i])
                {
                case '(':               //左括号优先级最低，直接进栈
                    optr.push(0);
                    break;
                case '+':                   //加减号，若操作符栈顶是加减号，则退栈然后进栈；否则直接进栈
                    if(optr.top() != 0)
                    {
                        temp1 = opnd.top();
                        opnd.pop();
                        temp2 = opnd.top();
                        opnd.pop();
                        temp = temp2 + optr.top() * temp1;
                        opnd.push(temp);
                        optr.pop();
                    }
                    optr.push(1);
                    break;
                case '-':
                    if(optr.top() != 0)
                    {
                        temp1 = opnd.top();
                        opnd.pop();
                        temp2 = opnd.top();
                        opnd.pop();
                        temp = temp2 + optr.top() * temp1;
                        opnd.push(temp);
                        optr.pop();
                    }
                    optr.push(-1);
                    break;
                case ')':               //遇见右括号一直退栈直至遇见左括号
                    while(1)
                    {
                        if(optr.top() == 0)
                        {
                            optr.pop();
                            break;
                        }
                        else
                        {
                            temp1 = opnd.top();
                            opnd.pop();
                            temp2 = opnd.top();
                            opnd.pop();
                            temp = temp2 + optr.top() * temp1;
                            opnd.push(temp);
                            optr.pop();
                        }
                    }
                    break;
                default:
                    break;
                }
            }

        }
        return opnd.top();      //最后操作数栈顶即为表达式值
    }
};