SDIBT2666——逆波兰表达式求值

逆波兰表达式求值(栈和队列)

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 ;
}
上一篇:【SimpleMsgPack.NET】发布一个msgpack协议C#版本的解析开源库


下一篇:【NOIP2013】Day2不完全题解+代码