后缀转中缀

练练手

题面

经典题,将整数计算的后缀表达式转化为中缀表达式并输出结果。

难点在于字符串的处理,由于没有给辅助信息,因此必须对输入的字符串进行分析。

这里用的是经典解法,注意这个数值计算和表达式转化虽然原理类似,但是要通过两个栈分别处理

(听说也有建树解的,不是很清楚怎么写,这里不给出解法了)

(split很常用,写法要记住)

#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#define MAXN 1000
using namespace std;
int n = 0;
string slist[MAXN];
void split(const string s)
{
    int cp = 0;
    int np = 0;
    while (np != s.npos)
    {
        np = s.find(' ', cp);
        slist[n] = s.substr(cp, np - cp);
        n++;
        cp = np + 1;
    }
}
double stringtodouble(string s)
{
    stringstream ss;
    ss << s;
    double d;
    ss >> d;
    return d;
}
int main()
{
    string s;
    getline(cin, s);
    split(s);
    stack<string> forms;
    stack<double> nstack;
    for (int i = 0; i < n; i++)
    {
        if (slist[i][0] == '+')
        {
            double a = nstack.top();
            nstack.pop();
            double b = nstack.top();
            nstack.pop();
            nstack.push(b + a);
            string as = forms.top();
            forms.pop();
            string bs = forms.top();
            forms.pop();
            forms.push("(" + bs + "+" + as + ")");
        }
        else if (slist[i][0] == '-')
        {
            double a = nstack.top();
            nstack.pop();
            double b = nstack.top();
            nstack.pop();
            nstack.push(b - a);
            string as = forms.top();
            forms.pop();
            string bs = forms.top();
            forms.pop();
            forms.push("(" + bs + "-" + as + ")");
        }
        else if (slist[i][0] == '*')
        {
            double a = nstack.top();
            nstack.pop();
            double b = nstack.top();
            nstack.pop();
            nstack.push(b * a);
            string as = forms.top();
            forms.pop();
            string bs = forms.top();
            forms.pop();
            forms.push(bs + "*" + as);
        }
        else if (slist[i][0] == '/')
        {
            double a = nstack.top();
            nstack.pop();
            double b = nstack.top();
            nstack.pop();
            nstack.push(b / a);
            string as = forms.top();
            forms.pop();
            string bs = forms.top();
            forms.pop();
            forms.push(bs + "/" + as);
        }
        else
        {
            nstack.push(stringtodouble(slist[i]));
            forms.push(slist[i]);
        }
    }
    cout << forms.top();
    cout << "=";
    cout << nstack.top();
    return 0;
}
Subscribe
提醒
guest
1 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments