biaodashi.cpp

该程序为从原四则表达式求得后缀表达式

#include "stdio.h"
#include "stdlib.h"
#define MAX_SIZE 100

typedef struct
{
	int *base;
	int *top;
}SqStack;

void InitStack(SqStack &S)
{
	S.base = (int *)malloc(MAX_SIZE * sizeof(int));
	S.top = S.base;
}

int GetTop(SqStack S)
{
	return *(S.top - 1);
}

void Push(SqStack &S,int e)
{
	*S.top++ = e;
}

int Pop(SqStack &S)
{
	S.top--;
	return *S.top;
}

bool isEmpty(SqStack S)
{
	if (S.base == S.top)
		return true;
	return false;
}

int Precede(int a,int b) //1为b>a,0为=,-1为b<a; b为当前运算符,a为栈顶运算符
{
	if ((a == '+') || (a == '-'))
	{
		if ((b == '+') || (b == '-'))
			return -1;  //a,b同加减,要出栈,优先级低
		if ((b == '*') || (b == '/'))
			return 1;
		if (b == '(')
			return 1;
		if (b == '#')
			return -1;
	}
	else if ((a == '*') || (a == '/'))
	{
		if ((b == '+') || (b == '-'))
			return -1;
		if ((b == '*') || (b == '/'))
			return -1;
		if (b == '(')
			return 1;
		if (b == '#')
			return -1;
	}
	else if (a == '(')  //又括号在主函数里另处理
	{
		return -1;
	}
	else if (a == '#')
	{
		return 1;
	}
}

void main()
{
	SqStack optr;
	InitStack(optr);
	printf("请输入表达式,以#开始和结束:\n");
	char ch,tmp;
	scanf("%c",&ch);
	Push(optr,ch);
	scanf("%c",&ch);
	while (ch != '#')
	{
		//是操作数直接打印
		if (((ch >= '0') && (ch <= '9')) || ((ch >= 'a') && (ch <= 'z')))
		{
			printf("%c",ch);
			scanf("%c",&ch);
		}
		else if (ch == ')')
		{
			tmp = GetTop(optr); 
			while (tmp != '(')
			{
				tmp = Pop(optr);
				printf("%c",tmp);
				tmp = GetTop(optr);
			}
			tmp = Pop(optr);
			scanf("%c",&ch);  //处理完左括号,右括号不要,读入下一个字符
		}
		else
		{
			switch(Precede(GetTop(optr),ch))
			{
			case 1:  //优先级高则如栈
				Push(optr,ch);
				scanf("%c",&ch);
				break;
			case -1:	//出栈所有优先级比当前高的运算符 
				tmp = GetTop(optr);
				while ((tmp != '#') && (tmp != '(')
					&& (Precede(GetTop(optr),ch) == -1))
				{
					tmp = Pop(optr);
					printf("%c",tmp);
					tmp = GetTop(optr);
				}
				if (tmp == '(')
				{
					Push(optr,ch);
					scanf("%c",&ch);
				}
			}
		}	
	}

	//输入为'#'结束时,把栈中的运算符全部弹出
	tmp = GetTop(optr);  
	while (tmp != '#')
	{
		tmp = Pop(optr);
		printf("%c",tmp);
		tmp = GetTop(optr);
	}
	printf("\n");
}