题解 | #四则运算#

#include <iostream>
#include <stack>
#include <string>


using namespace std;
void backtracking(stack<double>& num, stack<char>& str)
{
    //第一步，将下一个括号前的乘法和除法完成掉
    stack<double> num_temp;
    stack<char> str_temp;
    num_temp.push(num.top());
    num.pop();
    while ((!(str.empty()))  &&   ( str.top() != '(' )    )
    {
        if (str.top() == '*')
        {
            double temp = (num_temp.top()) * (num.top());
            num_temp.pop();
            num.pop();
            num_temp.push(temp);
            str.pop();
        }else if (str.top() == '/')
        {
            double temp = (num.top()) / (num_temp.top());
            num_temp.pop();
            num.pop();
            num_temp.push(temp);
            str.pop();
        }else if (str.top() == '+')
        {
            str_temp.push(str.top());
            str.pop();
            num_temp.push(num.top());
            num.pop();
        }else if (str.top() == '-')
        {
            str_temp.push(str.top());
            str.pop();
            num_temp.push(num.top());
            num.pop();
        }
        
    }
    //搞完这些循环以后，临时的栈就剩下加减
    int value = num_temp.top();
    num_temp.pop();
    while (!(str_temp.empty()))
    {
        if (str_temp.top() == '+')
        {
            value = value + num_temp.top();
            num_temp.pop();
            str_temp.pop();
        }else if (str_temp.top() == '-')
        {
            value = value - num_temp.top();
            num_temp.pop();
            str_temp.pop();
        }
    }
    //这个时候，括号的内的所有值都算出来了，str的栈顶是“）”
    if (!(str.empty()))
    {
        str.pop();
    }
    num.push(value);

}

int main()
{
    string ss;
    cin >> ss;
    //ss就是一个算术式子
    for (int i = 0;i < ss.size();i++)
    {
        if (ss[i] == '{' || ss[i] == '[')
        {
            ss.replace(ss.begin() + i, ss.begin() + i, "(");
        }
        if (ss[i] == '}' || ss[i] == ']')
        {
            ss.replace(ss.begin() + i, ss.begin() + i, ")");
        }
    }
    stack<double> num;//存数字
    stack<char> str;//存运算符和括号
    if (ss[0] == '-')
    {
        num.push(0);
    }
    string aa = "";
    for (int i = 0;i < ss.size();i++)
    {
        if (ss[i] >= '0' && ss[i] <= '9')
        {//找到下一个非数字位
            int j = i;
            while( ss[j+1] >= '0' && ss[j+1] <= '9' && j+1 != ss.size())
            {
                j++;
            }
            aa = ss.substr(i,j-i+1);
            int tt = stoi(aa);
            num.push(double(tt));
            aa = "";
            i = j;
        }
        else {
            if (ss[i] != ')')
            {
                str.push(ss[i]);
            }
            if (ss[i] == '(' && (ss[i + 1] < '0' || ss[i + 1] > '9'))
            {
                num.push(0);
            }
            if (ss[i] == ')')
            {
                backtracking(num, str);
                //该函数需要完成的任务是，将直到下一个括号之前的所有值
            }
        }
        
    }
    //现在只剩下一个加减了
    if (!(num.empty()))
    {
        backtracking(num, str);
    }
    cout << num.top() << endl;
    system("pause");
    return 0;
}
#栈#