中后缀表达式/洛谷P1175 表达式的转换

思路：先用栈转成中缀表达式，再用栈进行计算。要输出过程，因此计算一次输出一次，但是栈没有迭代器，不好用，换成vector（可以pop_back）。虽然表达式求值也可以这么做，但是还是直接做比较简单。

#include<bits/stdc++.h>

using namespace std;

unordered_map<char,int>mp;

int calc(int a,int b,char opt) {

    if(opt=='+')return a+b;

    if(opt=='-')return a-b;

    if(opt=='*')return a*b;

    if(opt=='/')return a/b;

    if(opt=='^')return pow(a,b);

}

string s;

bool isd(char c){return (c>='0'&&c<='9');}

string change(string s)

{

    stack<char>st;

    string res="";

    int len=s.length();

    for(int i=0;i<len;++i)

    {

        if(isd(s[i]))res+=s[i];

        else if(s[i]=='(')st.push(s[i]);

        else if(s[i]==')')

        {

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

                res+=st.top(),st.pop();

            st.pop();

        }

        else

        {

            while(!st.empty()&&mp[st.top()]>=mp[s[i]])

                res+=st.top(),st.pop();

            st.push(s[i]);

        }

    }

    while(!st.empty())res+=st.top(),st.pop();

    return res;

}

void print(string s)

{

    int len=s.length();

    for(int i=0;i<len;++i)

        printf("%c ",s[i]);

    puts("");

}

void solve(string s)

{

    print(s);

    vector<int>v;

    int len=s.length();

    for(int i=0;i<len;++i)

    {

        if(isd(s[i]))v.push_back(s[i]-'0');

        else

        {

            int x=v.back();v.pop_back();

            int y=v.back();v.pop_back();

            v.push_back(calc(y,x,s[i]));

            for(int j=0;j<v.size();++j)printf("%d ",v[j]);

            for(int j=i+1;j<len;++j)printf("%c ",s[j]);

            puts("");

        }

    }

}

int main()

{

    mp['(']=mp[')']=0;mp['+']=mp['-']=1;mp['*']=mp['/']=2;mp['^']=3;

    cin>>s;

    s=change(s);

    solve(s);

    return 0;

}

巴特西

中后缀表达式/洛谷P1175 表达式的转换

最新文章

热门文章