逆波兰表达式求值（栈和队列）
Description
从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以@符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：
请输入一个以'@'字符结束的中缀算术表达式：12+(3*(20/4)-8)*6@
对应的后缀算术表达式为：
12 3 20 4 /*8 -6 *+@
求值结果为：54
Input
12+(3*(20/4)-8)*6@
Output
54
中序表达式转换为逆波兰表达式:
从中缀式的左端开始取字符，逐序进行如下步骤（需要一个栈S1和一个数组）
（1）若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入数组
（2）若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符优先级大于S1栈栈顶运算符优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入数组中，直至S1栈栈顶运算符低于（不包括等于）该运算符优先级，则将该运算符送入S1栈。
（3）若取出的字符是“（”，则直接送入S1栈栈顶。
（4）若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入数组，此时抛弃“（”。
（5）重复上面的1~4步，直至处理完所有的输入字符
（6）若取出的字符是“#”，则将S1栈内所有运算符（不包括“@”），逐个出栈，依次送入数组。
逆波兰表达式计算：
新建一个表达式,如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。
PS：
注意最后一个数字的处理！！
Code：
1 #include<stdio.h> 2 #define MAXN 10000 3 typedef struct Stack 4 { 5 int date[MAXN]; 6 int top; 7 } Stack; 8 struct BL 9 { 10 int date; 11 int ischar; //计算时 判断是运算符还是数值 12 } a[1000]; 13 Stack s1; 14 void Stack_Init(Stack *S) 15 { 16 S->top=-1; 17 } 18 int IsEmpty(Stack *S) 19 { 20 if (S->top==-1) return 1; 21 return 0; 22 } 23 void push(Stack *S,int tmp) 24 { 25 S->top++; 26 S->date[S->top]=tmp; 27 } 28 int pop(Stack *S) 29 { 30 int tmp; 31 tmp=S->date[S->top]; 32 S->top--; 33 return tmp; 34 } 35 int top(Stack *S) 36 { 37 return S->date[S->top]; 38 } 39 int main() 40 { 41 char tmp; 42 int i=0,j,num=0,t,t1,t2; 43 Stack_Init(&s1); 44 while (scanf("%c",&tmp)!=EOF) 45 { 46 if (tmp=='@') 47 { 48 if (num) 49 {a[i].date=num; 50 a[i++].ischar=0;} 51 break; 52 } 53 if (tmp>='0'&&tmp<='9') num=num*10+tmp-48; 54 else 55 { 56 if (num) 57 { 58 a[i].date=num; 59 num=0; 60 a[i++].ischar=0; 61 } 62 if (tmp=='(') push(&s1,tmp); 63 else if (tmp==')') 64 { 65 while (top(&s1)!='(') 66 { 67 t=pop(&s1); 68 a[i].date=t; 69 a[i++].ischar=1; 70 } 71 pop(&s1); 72 } 73 else if (tmp=='+'||tmp=='-') 74 { 75 while (IsEmpty(&s1)!=1&&top(&s1)!='(') 76 { 77 t=pop(&s1); 78 a[i].date=t; 79 a[i++].ischar=1; 80 } 81 push(&s1,tmp); 82 } 83 else if (tmp=='*'||tmp=='/') 84 { 85 while (IsEmpty(&s1)!=1&&(top(&s1)!='+'&&top(&s1)!='-')&&top(&s1)!='(') 86 { 87 t=pop(&s1); 88 a[i].date=t; 89 a[i++].ischar=1; 90 } 91 push(&s1,tmp); 92 } 93 } 94 } 95 while (IsEmpty(&s1)!=1) 96 { 97 t=pop(&s1); 98 a[i].date=t; 99 a[i++].ischar=1; 100 } 101 for (j=0; j<i; j++) 102 if (a[j].ischar) 103 { 104 t1=pop(&s1);t2=pop(&s1); 105 if (a[j].date=='*'){t1=t2*t1;push(&s1,t1);} 106 if (a[j].date=='/'){t1=t2/t1;push(&s1,t1);} 107 if (a[j].date=='+'){t1=t2+t1;push(&s1,t1);} 108 if (a[j].date=='-'){t1=t2-t1;push(&s1,t1);} 109 } 110 else push(&s1,a[j].date); 111 printf("%d",top(&s1)); 112 return 0; 113 }