内存:1000  时间:1

题目描述

从键盘上输入一个逆波兰表达式,用伪码写出其求值程序。规定:逆波兰表达式的长度不超过一行,以@符作为输入结束,操作数之间用空格分隔,操作符只可能有+*/四种运算。例如:

请输入一个以‘@’字符结束的中缀算术表达式:
12+(3*(20/4)-8)*6@
对应的后缀算术表达式为:
12 3 20 4 /*8 -6 *+@
求值结果为:54

输入

输入:

12+(3*(20/4)-8)*6@

输出

输出:

54

样例输入

12+(3*(20/4)-8)*6@

样例输出

54

提示

代码如下

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define SEN 100

struct sqstack
{
	int *base;
	int *top;
	int size;
};

struct sqstack *initEmptyStack()
{
	struct sqstack *p;
	p=(struct sqstack *)malloc(sizeof(struct sqstack));
	if(p!=NULL)
	{
		p->base=(int *)malloc(sizeof(struct sqstack)*SEN);
		if(p->base!=NULL)
		{
			p->top=p->base;
			p->size=SEN;
			return p;
		}
	}
	else
		free(p);
	return NULL;
}

int push(struct sqstack *p,int a)
{
	*p->top++=a;
	return 0;
}
char compare(char a,char b)
{
	if(a=='['||a=='(') 
		return '>';
	else if((a=='+'||a=='-')&&(b=='+'||b=='-')&&b!=']'&&b!=')')
		return '<';
	else if((a=='+'||a=='-')&&b!='+'&&b!='-'&&b!=']'&&b!=')')
		return '>';
	else if((a=='*'||a=='/')&&(b=='['||b=='('))
		return '>';
	else if((a=='*'||a=='/')&&b!='['&&b!='(')
		return '<';
	else if(b==')'||b==']')
		return '<';
	return 0;
}


int gettop(struct sqstack *p)
{
	if(p->base!=p->top)
		return *(p->top-1);
	return 0;
}
int pop(struct sqstack *p)
{
	
	
        if(p->base!=p->top)
                return *(--p->top);
		return 0;
}

int zhuanghuan(char b[10])
{
	int sum=0,i=0,k;
	k=strlen(b);
	while(k--)
	{
		sum=sum*10+(b[i]-48);
		i++;
	}
	return sum;
}

int main()
{
	char c,d,e,a[100]={0},b[10];
	int sum;
	int p,q,i,j,t1,t2,f,k;
	struct sqstack *p1,*p2;
	p1=initEmptyStack();
	p2=initEmptyStack();
	gets(a);
	k=strlen(a);
	for(i=0;a[i]!='@';)
	{
		t1=0;
		t2=0;
		if(a[i]<'0'||a[i]>'9')
		{
			c=a[i];
			i++;
			t1=1;
		}
		else
		{
			for(j=0;j<10;j++)
				b[j]=0;
			j=0;
			while((a[i]>='0'&&a[i]<='9')&&i<k-1)
			{
				b[j]=a[i];
				i++;
				j++;
			}
			f=zhuanghuan(b);
			t2=1;
		}	
		if(t2==1)
			push(p2,f);	
		if(t1==1)
		{
			if(p1->base!=p1->top)
			{
				d=gettop(p1);
				e=compare(d,c);
				switch(e)
				{
				case '>':
					{
						push(p1,c);	
						break;
					}
				case '<':
					{
						p=pop(p2);
						q=pop(p2);
						if(d=='+')
							sum=p+q;
						else if(d=='-')
							sum=q-p;
						else if(d=='*')
							sum=p*q;
						else
							sum=q/p;
						push(p2,sum);
						pop(p1);
						
						
						
						
						if(c==']'||c==')')	
						{
							while(gettop(p1)!='['&&gettop(p1)!='('&&p1->base!=p1->top)
							{
								d=pop(p1);
								if(d!='['&&d!='(')
								{
									p=pop(p2);
									q=pop(p2);
									if(d=='+')
										sum=p+q;
									else if(d=='-')
										sum=q-p;
									else if(d=='*')
										sum=p*q;
									else if(d=='/')
										sum=q/p;
									else
									{}
								}
								else
								{}
								push(p2,sum);
								if(p1->base!=p1->top)
									pop(p1);
							}
							if(p1->base!=p1->top)
								pop(p1);
						}
						if(c!=']'&&c!=')')
							push(p1,c);
						break;	
					}
				}
			}
			else
				push(p1,c);
		}
		//	}
	}
	while((p1->base!=p1->top))
	{
		d=pop(p1);
		if(d!='['&&d!='(')
		{
			p=pop(p2);
			q=pop(p2);
			if(d=='+')
				sum=p+q;
			else if(d=='-')
				sum=q-p;
			else if(d=='*')
				sum=p*q;
			else if(d=='/')
				sum=q/p;
			else
			{}
		}
		else
		{}
		push(p2,sum);
	}
	printf("%d\n",pop(p2));
	return 0;
}

代码来源于互联网,仅供参考!