逆波兰表达式求值（栈和队列）
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：
#include<stdio.h>
#define MAXN 10000
typedef struct Stack
{
int date[MAXN];
int top;
} Stack;
struct BL
{
int date;
int ischar; //计算时 判断是运算符还是数值
} a[];
Stack s1;
void Stack_Init(Stack *S)
{
S->top=-;
}
int IsEmpty(Stack *S)
{
if (S->top==-) return ;
return ;
}
void push(Stack *S,int tmp)
{
S->top++;
S->date[S->top]=tmp;
}
int pop(Stack *S)
{
int tmp;
tmp=S->date[S->top];
S->top--;
return tmp;
}
int top(Stack *S)
{
return S->date[S->top];
}
int main()
{
char tmp;
int i=,j,num=,t,t1,t2;
Stack_Init(&s1);
while (scanf("%c",&tmp)!=EOF)
{
if (tmp=='@')
{
if (num)
{a[i].date=num;
a[i++].ischar=;}
break;
}
if (tmp>=''&&tmp<='') num=num*+tmp-;
else
{
if (num)
{
a[i].date=num;
num=;
a[i++].ischar=;
}
if (tmp=='(') push(&s1,tmp);
else if (tmp==')')
{
while (top(&s1)!='(')
{
t=pop(&s1);
a[i].date=t;
a[i++].ischar=;
}
pop(&s1);
}
else if (tmp=='+'||tmp=='-')
{
while (IsEmpty(&s1)!=&&top(&s1)!='(')
{
t=pop(&s1);
a[i].date=t;
a[i++].ischar=;
}
push(&s1,tmp);
}
else if (tmp=='*'||tmp=='/')
{
while (IsEmpty(&s1)!=&&(top(&s1)!='+'&&top(&s1)!='-')&&top(&s1)!='(')
{
t=pop(&s1);
a[i].date=t;
a[i++].ischar=;
}
push(&s1,tmp);
}
}
}
while (IsEmpty(&s1)!=)
{
t=pop(&s1);
a[i].date=t;
a[i++].ischar=;
}
for (j=; j<i; j++)
if (a[j].ischar)
{
t1=pop(&s1);t2=pop(&s1);
if (a[j].date=='*'){t1=t2*t1;push(&s1,t1);}
if (a[j].date=='/'){t1=t2/t1;push(&s1,t1);}
if (a[j].date=='+'){t1=t2+t1;push(&s1,t1);}
if (a[j].date=='-'){t1=t2-t1;push(&s1,t1);}
}
else push(&s1,a[j].date);
printf("%d",top(&s1));
return ;
}