题解 | #表达式求值#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int convert2number(vector<char> vec)
    {
        int length = vec.size();
        int ret = 0, mid= 0;
        for(int i=0; i<length; i++)
        {
            if(vec[i]!='0')
            { 
                mid = vec[i]-'0';
                ret = ret*10 + mid;
            }
            else
            {
                ret = ret*10;
            }
        }
        return ret;
    }
    int solve(string s) {
        // write code here
        stack<char> str_stack;
        vector<char> vec;
        vector<int> number;
        stack<int> calculate;
        int length = s.length();
        string str;
        vector<char> vec_char;
        // 计算逆波兰表达式
        for(int i=0; i<length; i++)
        {
            switch (s[i])
            {
                case '+':
                    {
                        if(!str_stack.empty()&&str_stack.top() =='*')
                        {
                            while(!str_stack.empty()&&str_stack.top()!='(')
                            {
                                vec.push_back(',');
                                vec.push_back(str_stack.top());
                                str_stack.pop();
                            }
                        }
                        if(!str_stack.empty()&&(str_stack.top()=='-'||str_stack.top()=='-'))
                        {
                            vec.push_back(',');
                            vec.push_back(str_stack.top());
                            str_stack.pop();
                        }
                        vec.push_back(',');
                        str_stack.push(s[i]);
                        break;    
                    }
                case '-':
                    if(!str_stack.empty()&&str_stack.top()=='*')
                    {
                        while(!str_stack.empty()&&str_stack.top()!='(')
                        {
                            vec.push_back(',');
                            vec.push_back(str_stack.top());
                            str_stack.pop();
                        }
                    }
                    if(!str_stack.empty()&&(str_stack.top()=='-'||str_stack.top()=='-'))
                    {
                        vec.push_back(',');
                        vec.push_back(str_stack.top());
                        str_stack.pop();
                    }
                    vec.push_back(',');
                    str_stack.push(s[i]);
                    break;
                case '*':
                    { 
                        vec.push_back(','); // 加上一个分割符号
                        if(!str_stack.empty()&&str_stack.top()=='*')
                        {
                            vec.push_back(str_stack.top());
                            str_stack.pop();
                        }
                        str_stack.push(s[i]);
                        break;
                    }
                case '(':
                    str_stack.push(s[i]);
                    break;
                case ')':
                    {
                        auto ptr = str_stack.top();
                        while(!str_stack.empty()&&ptr!='(')
                        {
                            vec.push_back(',');
                            vec.push_back(ptr);
                            str_stack.pop();
                            ptr = str_stack.top();
                        }
                        str_stack.pop(); // 出栈（
                        break;
                    }
                default:
                    vec.push_back(s[i]);
                    break;
            }
        }
        while(!str_stack.empty())
        {
            vec.push_back(',');
            vec.push_back(str_stack.top());
            str_stack.pop();
        }
        // 得到逆波兰表达式后运算
        for(int j = 0; j < vec.size(); j++)
        {
            switch(vec[j])
            {
                case '-':
                    {
                        int a = calculate.top();
                        calculate.pop();
                        int b = calculate.top();
                        calculate.pop();
                        int c = b - a;
                        calculate.push(c);
                        break;
                    }
                case '+':
                    {
                        int a = calculate.top();
                        calculate.pop();
                        int b = calculate.top();
                        calculate.pop();
                        int c = a + b;
                        calculate.push(c);
                        break;
                    }
                case '*':
                    {
                        int a = calculate.top();
                        calculate.pop();
                        int b = calculate.top();
                        calculate.pop();
                        int c = a * b;
                        calculate.push(c);
                        break;
                    }
                case ',':
                    if(!vec_char.empty())
                    {
                        auto num = convert2number(vec_char);
//                         number.push_back(num);
                        calculate.push(num);
                        vec_char.clear();
                    }
                    break; // 如果是逗号分割符的话，就直接不管他了，跳过，下一个
//                     vec.pop_back();  // 如果是逗号分割符的话，就直接剔除
                default:
                    {
                        vec_char.push_back(vec[j]);
//                         auto num = convert2number(vec_char);
//                         number.push_back(num);
//                         vec_char.clear();
//                         calculate.push(vec[j] - '0');
                        break;
                    }
            }
        }
        return calculate.top();
    }
};