数据结构实验之栈三：后缀式求值

数据结构实验之栈三：后缀式求值

Time Limit: 1000MS Memory Limit: 65536KB

Submit Statistic

Problem Description

对于一个基于二元运算符的后缀表示式（基本操作数都是一位正整数），求其代表的算术表达式的值。

Input

输入一个算术表达式的后缀式字符串，以‘#’作为结束标志。

Output

求该后缀式所对应的算术表达式的值，并输出之。

Example Input

59*684/-3*+#

Example Output

57

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define stack_size 1000
#define stackincreament 100
typedef int element;
typedef struct
{
	element *base;
	element *top;
	int stacksize;
}Stack;
int initializer_list(Stack &S)
{
    S.base = (element *)malloc(sizeof(element)*stack_size);
    if(!S.base) exit(-1);
    S.top = S.base;
    S.stacksize = stack_size;
    return 1;
}
int push(Stack &S,int &e)
{
	if(S.top - S.base >=S.stacksize)
	{
		S.base = (element *)realloc(S.base,(sizeof(element)*(S.stacksize+stackincreament)));
		if(S.base) exit(-1);
		S.top = S.base + S.stacksize;
		S.stacksize +=stackincreament;
	}

	*S.top++ = e;
	return 0;
}
int pop(Stack &S)
{
	if(S.base==S.top)
	{
		return -1;
	}
	S.top--;
	return 0;
}
void change(Stack &S,char str[])
{
	int i=0;
	int a,b,c;
	while(str[i]!='#')
	{
		if(str[i]>='0' && str[i]<='9')
		{
			c = str[i]-'0';
			push(S,c);
		}
		else if(str[i]=='*')
		{
			pop(S);
			b = *S.top;
			if(S.base!=S.top)
			{
                pop(S);
				a = *S.top;
			}
			c = a*b;	
			push(S,c);
		}
		
	   	else if(str[i]=='/')
		{
				pop(S);
			b = *S.top;
			if(S.base!=S.top)
			{
                pop(S);
				a = *S.top;
			}
			c = a/b;//	printf("c==%c\n",c);
			push(S,c);
		}
		else if(str[i]=='+')
		{
		   	pop(S);
			b = *S.top;
			if(S.base!=S.top)
			{
                pop(S);
				a = *S.top;
			}
			c = a+b;	//printf("c==%c\n",c);
			push(S,c);
		}
		else if(str[i]=='-')
		{
				pop(S);
			b = *S.top;
			if(S.base!=S.top)
			{
                pop(S);
				a = *S.top;
			}
			c = a-b;
			//printf("c==%d\n",c);
			push(S,c);
		}
		i++;
	}
	while(S.base!=S.top)
	{
		pop(S);
		printf("%d\n",*S.top);
	}
	printf("\n");
}
int main()
{
    Stack S;
    initializer_list(S);
	char string[123];
	scanf("%s",string);
	change(S,string);
	
	return 0;
}