题解 | #表达式求值#

#include<iostream>
#include<stack>
#include<string>
#include<vector>
using namespace std;
int main(int argc,char* argv[])
{
    //思路：
    //第一部分:构建逆波兰表达是数组
    //构建原则:
        //1、遍历表达式字符串
            //遇到左括号和乘除 无条件入栈
            //遇到加减 把栈顶的乘除加减都弹出后再入栈
                //(注意减号:当其前面为左括号或者无符号(i==0)时，需要补充一个0，否则需要当负数处理，入栈时该数需要添加负号)
            //遇到 右括号 需要一直弹出栈顶加减乘除元素直至栈顶元素为左括号 （弹出当前的栈顶的左括号）
            //其他情况 则为数值
                //这里需要考虑 自然数大于个位数的情况，比如 100不能视为3个数而应该是单个数
                                     // 0-9 的 ASCII 码为 48-57
        //2、遍历栈内符号 弹出栈内所有的加减乘除元素
    //第二部分:逆波兰表达式求值
    //1、遍历逆波兰表达式 数组就入栈，符号就弹出2个栈顶元素 执行操作后再入栈
    //2、此时栈顶元素就是最终表达式的结果值
    
    string expressionStr="";
    while(getline(cin,expressionStr))
    {
        vector<string> expressionVec;//表达式
        stack<char> symbolSt;//符号栈
        for(int i=0;i<expressionStr.length();i++)
        {
            if(expressionStr[i] =='(' || expressionStr[i] =='[' || expressionStr[i] =='{' || expressionStr[i] =='*' || expressionStr[i] =='/') symbolSt.push(expressionStr[i]);
            else if(expressionStr[i] =='+' || expressionStr[i] =='-' )
            {
                if(expressionStr[i] =='-' && (i==0 || expressionStr[i-1] =='(' || expressionStr[i-1] =='[' || expressionStr[i-1] =='{' ))
                {
                    expressionVec.push_back("0");
                    symbolSt.push(expressionStr[i]);
                }
                else
                {
                    while(!symbolSt.empty() && (symbolSt.top()=='*' || symbolSt.top()=='/' || symbolSt.top()=='+' || symbolSt.top()=='-'))
                    {
                        if(symbolSt.top()=='*') expressionVec.push_back("*");
                        else if(symbolSt.top()=='/') expressionVec.push_back("/");
                        else if(symbolSt.top()=='+') expressionVec.push_back("+");
                        else if(symbolSt.top()=='-') expressionVec.push_back("-");
                        symbolSt.pop();
                    }
                    symbolSt.push(expressionStr[i]);
                }
            }
            else if(expressionStr[i] ==')' || expressionStr[i] ==']' || expressionStr[i] =='}')
            {
                while(!symbolSt.empty() && symbolSt.top() !='(' && symbolSt.top() !='[' && symbolSt.top() !='{')
                {
                    if(symbolSt.top()=='*') expressionVec.push_back("*");
                    else if(symbolSt.top()=='/') expressionVec.push_back("/");
                    else if(symbolSt.top()=='+') expressionVec.push_back("+");
                    else if(symbolSt.top()=='-') expressionVec.push_back("-");
                    symbolSt.pop();
                }
                symbolSt.pop();
            }
            else
            {
                string temp="";
                while(i<expressionStr.length()-1 && expressionStr[i+1]>=48 && expressionStr[i+1]<=57) temp+= expressionStr[i++];
                temp+= expressionStr[i];
                expressionVec.push_back(temp);
            }
        }
        while(!symbolSt.empty())
        {
            if(symbolSt.top()=='*') expressionVec.push_back("*");
            else if(symbolSt.top()=='/') expressionVec.push_back("/");
            else if(symbolSt.top()=='+') expressionVec.push_back("+");
            else if(symbolSt.top()=='-') expressionVec.push_back("-");
            symbolSt.pop();
        }
        stack<int> resultSt;
        for(int i=0;i<expressionVec.size();i++)
        {
            if(expressionVec[i] == "*" || expressionVec[i] == "/" || expressionVec[i] == "+" || expressionVec[i] == "-")
            {
                int temp1=resultSt.top();
                resultSt.pop();
                int temp2=resultSt.top();
                resultSt.pop();
                int temp3=0;
                if(expressionVec[i] == "*") temp3=temp2 * temp1;
                else if(expressionVec[i] == "/") temp3=temp2 / temp1;
                else if(expressionVec[i] == "+") temp3=temp2 + temp1;
                else if(expressionVec[i] == "-") temp3=temp2 - temp1;
                resultSt.push(temp3);
            }else resultSt.push(atoi(expressionVec[i].c_str()));
        }
        int res=resultSt.top();
        resultSt.pop();
        cout<<res<<endl;
    }
    return 0;
}