郁闷的C小加（一）
时间限制：1000ms | 内存限制：65535KB
难度：3
描述
我们熟悉的表达式如a+b、a+b*(c+d)等都属于中缀表达式。中缀表达式就是（对于双目运算符来说）操作符在两个操作数中间：num1 operand num2。同理，后缀表达式就是操作符在两个操作数之后：num1 num2 operand。ACM队的“C小加”正在郁闷怎样把一个中缀表达式转换为后缀表达式，现在请你设计一个程序，帮助C小加把中缀表达式转换成后缀表达式。为简化问题，操作数均为个位数，操作符只有+-*/和小括号。
输入第一行输入T，表示有T组测试数据（T<10）。每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个表达式。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。并且输入数据不会出现不匹配现象。输出每组输出都单独成行，输出转换的后缀表达式。样例输入21+2(1+2)*3+4*5样例输出
12+12+3*45*+
/**思路：使用一个栈，用来存放运算符；使用一个队列 ，后缀表达式；将输入的字符串从左到右扫描一遍，如果遇到数字，则直接进入队列；如果遇到“(”,直接进入栈，如果遇到“)”,将栈中的运算符出栈，进入队列；如果遇到'+','-','*','/',将当前遇到的运算符str[i]与栈头的运算符opt1.top()进行优先级比较， 如果str[i]的优先级小于opt1.top()的优先级，，则将opt1.top()入队，将str[i]进栈， */#include<stdio.h>#include<string.h>#include<algorithm>#include<stack>#include<queue>using namespace std;int t;char str[1010];//stack<char>opt1;//存放运算符的栈 //queue<char>opt2;//存放后缀表达式的队列 int compare(char op)//设置操作符的优先级 {if(op=='+'||op=='-'){return 1;}else if(op=='*'||op=='/'){return 2;}return 0;}int main(){stack<char>opt1;queue<char>opt2;scanf("%d",&t);getchar();while(t–){while(!opt1.empty())opt1.pop();while(!opt2.empty())opt2.pop();scanf("%s",str);int len=strlen(str);opt1.push('#');for(int i=0;i<len;i++){if(str[i]>='0'&&str[i]<='9'){opt2.push(str[i]);//如果是数字，直接入队}if(str[i]=='(')//遇到"("直接进栈{opt1.push(str[i]);}if(str[i]==')'){while(opt1.top()!='('){//char s1=opt1.top();//opt2.push(s1);opt2.push(opt1.top());opt1.pop();}opt1.pop();//最后把“(”出栈，但不输出}else if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'){char s=opt1.top();while(compare(str[i])<=compare(opt1.top()))//<=就可以，小于不可以，为什么？？不解！！{opt2.push(s);opt1.pop();s=opt1.top();}opt1.push(str[i]);}}while(!opt1.empty()){opt2.push(opt1.top());opt1.pop();}while(opt2.front()!='#')// 不以'#'结尾居然不对，不解？？？ {printf("%c",opt2.front());opt2.pop();}printf("\n");}return 0;}
不做任何解释。没有人明白，
