逆波兰表达式求值（栈和队列）

逆波兰表达式求值（栈和队列）

时间： 1ms        内存：1000M

描述：

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

请输入一个以'@'字符结束的中缀算术表达式：
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

提示：

参考答案（内存最优[752]）：

#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;
}

参考答案（时间最优[0]）：

#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;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。