算术表达式的转换
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
小明在学习了数据结构之后，突然想起了以前没有解决的算术表达式转化成后缀式的问题，今天他想解决一下。
因为有了数据结构的基础小明很快就解出了这个问题，但是他突然想到怎么求出算术表达式的前缀式和中缀式呢？小明很困惑。聪明的你帮他解决吧。
Input
输入一算术表达式，以\'#\'字符作为结束标志。（数据保证无空格,只有一组输入）
Output
输出该表达式转换所得到的前缀式 中缀式 后缀式。分三行输出，顺序是前缀式 中缀式 后缀式。
Sample Input
a*b+(c-d/e)*f#
Sample Output
+*ab*-c/def
a*b+c-d/e*f
ab*cde/-f*+
Hint
Source
思路：栈的存放并不是一下子把所有的东西都放进去，而是边操作边存放的
1.对于中缀表达式向前缀表达式的转换：需要两个栈，一个栈存储字母，另一个栈存储运算符；并且前缀表达式是从右向左开始的（后缀表达式是从左向右开始的）当遇到字母的时候，进栈1，当遇到运算符的时候，进栈2，这时候进栈2是有条件的：1.如果当前的运算符是加减，而栈2的top是乘除，这时候要把栈2的top元素转移到栈1中（注意这时候没有相等的情况，和后缀表达式不一样，后缀表达式还有两种情况是当前的元素是加减，栈顶的元素也是加减；当前的元素是乘除，栈顶的元素也是乘除）然后当前的元素进栈2；2.当当前的元素是左括号的时候要去找右括号，除了这两个括号之外，把他们之间的元素都放到栈1里面（后缀表达式是当前是左括号，去找右括号，并且左右括号之间的元素是输出，而不是进入另一个栈）；3.其他的情况入栈2就行了；之后把栈2里面的元素都给清到栈1里面，最后把栈1的元素都输出即可；
中缀表达式向后缀表达式转换：只需要一个栈，存放运算符；当遇到字母就输出，当遇到运算符就进栈，这里的进栈是有条件的：1.如果当前的元素是加减，栈顶的元素是乘除，栈顶元素先输出，当前元素入栈；或者当前的元素是加减，栈顶的元素也是加减；或者当前的元素是乘除，栈顶的元素也是乘除；同样的操作；2.如果当前的元素是右括号，就要去栈里面找左括号 ，并且输出除了左右括号之外的所有的运算符；3.其他的情况就是入栈了；最后把栈里面的所有元素都输出；
2.对于前缀表达式和后缀表达式的运算：后缀表达式：需要一个栈存放操作数，遇到一个运算符就要对栈顶元素和栈次元素进行操作，注意这里的操作是栈次元素对栈顶元素进行加减乘除，之后top要退一位，最后输出栈顶的值即可；
前缀表达式：是从右往左扫描操作数入栈，操作的时候是栈顶元素对栈次元素进行加减乘除的运算；最后输出栈顶元素即可；
#include <stdio.h> #include <stdlib.h> #include <string.h> int main() { char a[10001]; char b[10001]; char c[10001]; scanf("%s", a); int len, i, j; len = strlen(a); int top1, top2; top1 = top2 = 0; for(i = len - 2; i >= 0; i--) { if(a[i] >= 'a' && a[i] <= 'z') { top1++; b[top1] = a[i]; } else if(a[i] == '+' || a[i] == '-') { if(c[top2] == '*' || c[top2] == '/') { top1++; b[top1] = c[top2]; c[top2] = a[i]; } else { top2++; c[top2] = a[i]; } } else if(a[i] == '*' || a[i] == '/') { top2++; c[top2] = a[i]; } else if(a[i] == ')') { top2++; c[top2] = a[i]; } else if(a[i] == '(') { while(c[top2] != ')') { top1++; b[top1] = c[top2]; top2--; } top2--; } } for(i = 1; i <= top2; i++) { printf("%c", c[i]); } for(i = top1; i >= 1; i--) { printf("%c", b[i]); } printf("\n"); for(i = 0; i < len - 1; i++) { if(a[i] != '(' && a[i] != ')') { printf("%c", a[i]); } } printf("\n"); int top = 0; memset(b,0,sizeof(b)); for(i = 0; i < len - 1; i++) { if(a[i] >= 'a' && a[i] <= 'z') { printf("%c", a[i]); } else if(a[i] == '(') { top++; b[top] = '('; } else if(a[i] == ')') { while(b[top] != '(') { printf("%c", b[top]); top--; } top--; } else if(a[i] == '+' || a[i] == '-') { if(b[top] != '(' && top != 0) { printf("%c", b[top]); top--; } top++; b[top] = a[i]; } else if(a[i] == '*' || a[i] == '/') { if(b[top] == '*' || b[top] == '/') { printf("%c", b[top]); top--; } else { top++; b[top] = a[i]; } } } for(j = top; j >= 1; j--) { printf("%c", b[j]); } printf("\n"); return 0; }
