2523 - 中缀式转换
我们熟悉的表达式如a+b、a+b*(c+d)等都属于中缀表达式。
中缀表达式就是（对于双目运算符来说）操作符在两个操作数中间：num1 operand num2。
同理，后缀表达式就是操作符在两个操作数之后：num1 num2 operand。
前缀表达式则是操作符在两个操作数之前：operand num1 num2。
现在试图输入一个中缀表达式分别转换为后缀表达式和前缀表达式。现在请你设计一个程序完成题目要求。
为简化问题，操作数均为个位数，操作符只有+-*/ 和小括号
题目输入
第一行输入T，表示有T组测试数据（T<10）。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个表达式。这个表达式里只包含+-*/与小括号
这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。并且输入数据不会出现不匹配
现象。
题目输出
每组输出都单独成行，分别输出转换的后缀表达式和前缀表达式。
输入/输出样例
题目输入
2 1+2 (1+2)*3+4*5
题目输出
12+ +12 12+3*45*+ +*+123*45
C++解答
#include <cstdio> #include <cstring> #include <stack> using namespace std; struct node{ char v; struct node *l, *r; node(char c){ v = c; l = r = NULL; } }; stack<node*> p; // 操作数栈 stack<char> q; // 操作符栈 int len; char str[1010]; /* 将p栈顶两数与q栈顶一操作符构建一颗二叉树，并压入p栈 */ int getOrder(char c){ switch(c){ case '+': case '-': return 0; case '*': case '/': return 1; case '(': case ')': return 2; } } void buildNode(){ node *t1 = new node(0); node *t2 = new node(0); char s; t2 = p.top(); p.pop(); t1 = p.top(); p.pop(); s = q.top(); q.pop(); node *N = new node(s); N->l = t1; N->r = t2; p.push(N); } void PUSH(int &i){ node *t = new node(str[i]); p.push(t); } /* 根据中缀式构建表达式树 */ void buildTree(){ int i; for(i = 0; i < len; i++){ if(str[i] >= '0' && str[i] <= '9') PUSH(i); else if(str[i] == '(') q.push('('); else if(str[i] == ')'){ while(q.top() != '(') buildNode(); q.pop(); }else{//+-*/ while(!q.empty() && q.top()!='(' && getOrder(q.top()) >= getOrder(str[i])) buildNode(); q.push(str[i]); } } while(!q.empty()) buildNode(); } void PRTraverse(node *t){ if(t){ printf("%c",t->v); PRTraverse(t->l); PRTraverse(t->r); } } void POTraverse(node *t){ if(t){ POTraverse(t->l); POTraverse(t->r); printf("%c", t->v); } } int main(){ int k; scanf("%d", &k); while(k--){ scanf("%s", str); len = strlen(str); buildTree(); POTraverse(p.top()); printf("\n"); PRTraverse(p.top()); printf("\n"); p.pop(); } return 0; }