题解 | #表达式求值#

表达式求值是经典问题。

1. 将表达式由中辍转为后辍
   如将(3+2)*30*(4-1)转为3,2,+30,*4,1,-*。
   转换方法为，用一个栈stk保存运算符号。对表达式进行遍历，
   当访问到数字时，添加到后辍式。
   当访问到'('时，入栈，
   当访问到')'时，出栈到后辍式，直到遇到'('， 当访问到'+','-','*'时，先将栈中优先级高或等的符号出栈到后辍式，再将当前访问符号入栈。 最后将栈中符号全部出栈到后辍式
2. 根所后辍表达式求值
   这个就很简单了，用栈保存数字。对表达式进行遍历
   当访问到数字时，入栈
   当访问到'+','-','*'时，出栈两个数字进行相应运算后将结果入栈。
   栈顶数字即为最终结果。

class Solution {
public:
    bool isLessEqual(char ch1, char ch2)
    {
        if (ch2 == '(')
            return false;
        
        return (ch1 == '+' || ch1 == '-')
                || (ch2 == '*');
    }
    string getnumstr(const string &s, int &start)
    {
        int end = start + 1;
        while (end < s.size() && isdigit(s[end]))
        {
            end++;
        }

        string ret(s, start, end - start);

        start = end;
        if (end < s.size() && s[end] == ',')
        {
            start++;
        }
        
        return ret;
    }
    
    string mid2post(const string &s)
    {
        string post;
        stack<char> stk;
        int i = 0; 
        while (i < s.size())
        {
            if (isdigit(s[i]))
            {
                post += getnumstr(s, i); //change i
                post += ",";
            }
            else if (s[i] == '(')
            {
                stk.push(s[i]);
                i++;
            }
            else if (s[i] == ')')
            {
                while (!stk.empty() && stk.top() != '(')
                {
                    post += stk.top();
                    stk.pop();
                }

                if (stk.empty())
                {
                    cout << "no ( error" << endl;
                    return "";
                }

                stk.pop();                
                i++;
            }
            else
            {
                while (!stk.empty() && isLessEqual(s[i], stk.top()))
                {                    
                    post += stk.top();
                    stk.pop();
                }
                
                stk.push(s[i]);
                i++;                
            }          
            
        }
        
        while (!stk.empty())
        {                    
            post += stk.top();
            stk.pop();
        }

        return post;
    }

    int calcPost(const string &s)
    {
        stack<int> stk;
        int i = 0; 
        while (i < s.size())
        {
            if (isdigit(s[i]))
            {
                stk.push(stoi(getnumstr(s, i)));
                continue;
            }
            
            if (stk.empty())
            {
                cout << "error" << endl;
                return -2;
            }
            int num2 = stk.top();
            stk.pop();
            
            if (stk.empty())
            {
                cout << "error" << endl;
                return -3;
            }
            int num1 = stk.top();
            stk.pop();

            switch (s[i++])
            {
            case '+':
                stk.push(num1 + num2);
                break;
            case '-':
                stk.push(num1 - num2);
                break;
            case '*':
                stk.push(num1 * num2);
                break;
            default:
                cout << "error" << endl;
                return -4;
            }
        }
        
        return stk.top();
    }
    
    int solve(string s) {
        cout << s << endl;
        s = mid2post(s);
        cout << s << endl;
        return calcPost(s);
    }
};