PAT3-06. 式の変換

<pre name="code" class="cpp">#include<string>
#include<iostream>
#include<stack>
#include<sstream>
using namespace std;
stringstream ss;
string s;
int i;

bool isop(){
    char c=s[i];
    return c=='('||c==')'||c=='*'||c=='/'||c=='+'&&i&&s[i-1]!='('
                ||  c=='-'&&i&&s[i-1]!='(';
}
void printnumber(){
    ss<<' ';
    if(s[i]=='+')++i;
    if(s[i]=='-')ss<<s[i++];
    while(s[i]>='0'&&s[i]<='9'||s[i]=='.') ss<<s[i++];
}
int main(){
    int op[333] {0};
    op['+']=op['-']=1, op['*']=op['/']=2;
    stack<char>st;
    cin>>s;

    while(i<s.size())
    {
        if(!isop()) printnumber();
        else
        {
            char c=s[i++];
            if(c==')')
            {
                while(!st.empty()&&st.top()!='(')
                  {ss<<' '<<st.top(); st.pop(); }
                st.pop();
            }
            else
            {
                while(!st.empty()&&(op[c]==1&&op[st.top()]==1||
                                    op[c]==2&&op[st.top()]==2|| op[c]==1&&op[st.top()]==2))
                  {ss<<' '<<st.top(); st.pop(); }
                st.push(c);
            }
        }
    }
    while(!st.empty())
      {ss<<' '<<st.top(); st.pop(); }
    cout<<ss.str().substr(1);
    return 0;
}

似たような問題は、スタックで接尾辞式を計算することです.その論理は次のとおりです.
数字は処理せず、直接数字スタックにpushします.
符号は+-,*/,()の3種類に分けられ,それぞれ対応レベル123であると仮定する.シンボルスタックのシンボル+-*/出スタックはpopの2つの数字を意味し、計算後に結果をpushをデジタルスタックに入れ、(出スタックは処理しない)pushをシンボルスタックに入れない.
現在のシンボルスタックのトップシンボルがxであると仮定し、新しいシンボルyが1つ読み出されるたびに、2つのケースに分けられる.
一、yが)の場合、yはスタックに入る必要はありません.シンボルスタックは1つまでpopしています(popに出てきて、(popをスタックから出すのも)
二、yがそうでなければ、yは必ずスタックに入る.yは必ずスタックに入るのが鍵で、y pushを直接シンボルスタックに入れるか、x popを出してy pushをシンボルスタックに入れるかのどちらかです.xyのレベルの組み合わせは9種類あり、x popを出す必要がない場合はレベル別に6種類あります.例えばx、yはそれぞれ(*または(*または+*)、または/(または+*)ですが、x popを出す必要がある場合は3種類しかありません.xyはそれぞれ1級1級(すなわち++または--)、または2級2級2級(すなわち**または/)、または2級1級(すなわち*+または*-または/-または/-)、popが出てもこのような組み合わせであれば、ずっとpopしなければなりません.計算はすべて前から後なので、以前の記号が計算(出力)できるようにできるだけ早く計算しなければなりません.
また、2つの点があります.第1の空のスタックではpopは必要ありません.第2の最後のシンボルスタックには、空になるまでpopシンボルスタックが積み上げられている可能性があります.これにより、スタックシミュレーション接尾辞式を用いて接尾辞式を計算するプロセスがシミュレートされます.ここでスタックを出る動作を出力に変更すればよい