NYOJ 467 中缀式变后缀式

做了表达式求值那道题之后做的

时间限制：1000 ms  |  内存限制：65535 KB

难度：3

• 描写叙述

• 人们的日常习惯是把算术表达式写成中缀式，但对于机器来说更“习惯于”后缀式。关于算术表达式的中缀式和后缀式的论述一般的数据结构书都有相关内容可供參看。这里不再赘述，如今你的任务是将中缀式变为后缀式。

  • 输入

  • 第一行输入一个整数n，共同拥有n组測试数据（n<10)。

    
    每组測试数据仅仅有一行，是一个长度不超过1000的字符串，表示这个运算式的中缀式，每一个运算式都是以“=”结束。

    这个表达式里仅仅包括+-*/与小括号这几种符号。

    当中小括号能够嵌套使用。数据保证输入的操作数中不会出现负数。
    数据保证除数不会为0

  • 输出

  • 每组都输出该组中缀式对应的后缀式，要求相邻的操作数操作符用空格隔开。

  • 例子输入

  • 2
    1.000+2/4=
    ((1+2)*5+1)/4=

  • 例子输出

  • 1.000 2 4 / + =
    1 2 + 5 * 1 + 4 / =

#include <iostream>
#include <cstring>
#include <string>
#include <stack>
 
using namespace std;
 
int prio(char x)
{
    if('+'==x || '-'==x)
        return 1;
    else if('*'==x || '/'==x)
        return 2;
    return 0;
}
 
int main()
{
    int n,i;
    string s1,s2;
    stack<char> s;
    cin>>n;
    while(n--)
    {
        cin>>s1;
        s2="";
        for(i=0,s.push('=');i<s1.length()-1;i++)
        {
            if('('==s1[i])
                s.push(s1[i]);
            else if(')'==s1[i])
            {
                while(s.top()!='(')
                {
                    s2+=s.top();
                    s2+=' ';
                    s.pop();
                }
                s.pop();
            }
            else if('+'==s1[i] || '-'==s1[i] || '*'==s1[i] || '/'==s1[i])
            {
                while(prio(s.top())>=prio(s1[i]))    //!!!这个地方easy把 prio(s1[i]) 写成 s1[i]
                {
                    s2+=s.top();
                    s2+=' ';
                    s.pop();
                }
                s.push(s1[i]);
            }
            else
            {
                while(isdigit(s1[i]) || '.'== s1[i])
                    s2+=s1[i++];
                i--;
                s2+=' ';
            }
        }
        while(s.top()!= '=')
        {
            s2+=s.top();
            s2+=' ';
            s.pop();
        }
         
        s2+=s.top();
        s.pop();
 
        cout<<s2<<endl;
    }
    return 0;
}