题解 | #表达式求值#

//后缀表达式计算(逆波兰表达式计算)

int calculate(vector<string>& tokens)

{

    stack<int>st;

    for (auto& tmp : tokens)

    {

        if (tmp == "+" || tmp == "-" || tmp == "*" || tmp == "/")

        {

            int right = st.top();

            st.pop();

            int left = st.top();

            st.pop();

            switch (tmp[0])

            {

            case '+':

                st.push(left + right);

                break;

            case '-':

                st.push(left - right);

                break;

            case '*':

                st.push(left*right);

                break;

            case '/':

                st.push(left / right);

                break;

            }

        }

        else

        {

            st.push(stoi(tmp));

        }

    }

    return st.top();

}

//中缀转后缀

int solve(string s)

{

    //vstr是后续给后缀表达式计算的vector

    vector<string> vstr;

    //symbol处理操作数

    stack<char> symbol;

    int i = 0;

    while (i < s.size())

    {

        //ret表示数字，因为数字不只个位数，所以用string

        string ret;

        //ch获取s的每个字符，并判断是否是数字

        //如果是数字，再要拼接在ret，不是则代表符号

        char ch;

        while (i < s.size())

        {

            ch = s[i++];

            if (ch >= '0'&&ch <= '9')

            {

                //如果是数字，再要拼接在ret后

                ret += ch;

            }

            else

            {

                //不是则代表是符号，跳出这个循环

                break;

            }

        }

        //判断ret有没有数字，有的话就入栈

        if (!ret.empty())

        {

            vstr.push_back(ret);

        }

        //此时ch肯定存储符号

        //接下俩判断符号优先级

        //首先要判断是否是)，因为遇到)的话，就要直接开始出栈了

        if (ch == ')')

        {

            //一直出到'('

            while (symbol.top() != '(')

            {

                string tmp(1, symbol.top());

                vstr.push_back(tmp);

                symbol.pop();

            }

            //最后'('也要出掉

            symbol.pop();

        }

        else if (ch == '(')

        {

            symbol.push(ch);

        }

        else if (ch == '*' || ch == '/')

        {

            //乘除遇到乘除需要出栈

            while (!symbol.empty()&&symbol.top() != '+'&&symbol.top() != '-'&&symbol.top()!='(')

            {

                string tmp(1, symbol.top());

                vstr.push_back(tmp);

                symbol.pop();

            }

            symbol.push(ch);

        }

        else if(ch =='-' ||ch == '+')

        {

            //加减要一直出栈，直到栈空或者到'('

            while ((!symbol.empty()) && symbol.top() != '(')

            {

                string tmp(1, symbol.top());

                vstr.push_back(tmp);

                symbol.pop();

            }

            symbol.push(ch);

        }

    }

    //如果栈里面还有操作符，需要添加到vstr

    while (!symbol.empty())

    {

        string tmp(1, symbol.top());

        symbol.pop();

        vstr.push_back(tmp);

    }

    return calculate(vstr);

}