初级数据结构--栈在表达式求值的应用

表达式

一般有三部分组成：操作数、运算符、界限符

我们常见的表达式一般都属于中缀表达式，比如：2*2/(1+1)-4/2+1

后缀表达式

中缀表达式便于人的理解，但不便于计算机的处理。

于是便有了后缀表达式，也成逆波兰表达式。

比如上面表达式手动转为后缀表达式为2 2 * 1 1 + / 4 2 / - 1 +

（提一下不常用的前缀表达式比如桶为上中缀表达式：+ 1 - / 2 4 / + 1 1 * 2 2，右优先）

为保证运算顺序的唯一性，采用“左优先”的原则。

用栈实现后缀表达式计算

1. 初始化两个栈，一个栈存放运算符，一个栈存放操作数
2. 从左往右扫描下一个元素，直到扫描所有元素
3. 扫描到操作数压入操作数栈，扫描到运算符压入操作符栈

实战上代码

伪代码，或者说是一个bug

目前只支持整型正数，且不带括号的表达式运算，明天继续改善

typedef struct Operand
{
	int and[MAX_SIZE];
	int top;
}Operand;
typedef struct Operator
{
	int top;
	char ator[MAX_SIZE];
}Operator;

//初始化两个栈
void Init_Oper(Operand *p1, Operator *p2)
{
	int i = 0;
	for (i = 0; i < MAX_SIZE; i++)
	{
		p1->and[i] = 0;
		p2->ator[i] = 0;
	}
	p1->top = 0;
	p2->top = 0;
}
//计算
int Calculate(char ator,int x,int y)
{
	switch (ator)
	{
	case '+':
		return x + y;
		break;
	case '-':
		return x - y;
		break;
	case '*':
		return x*y;
		break;
	case '/':
		return x / y;
		break;
	default:
		break;
	}
}
void Out(Operand *p1, Operator *p2)
{
	int ret = 0;
	ret = Calculate(p2->ator[p2->top - 1],
		p1->and[p1->top - 2],
		p1->and[p1->top - 1]);
	p1->and[p1->top - 2] = ret;
	p1->and[p1->top - 1] = 0;
	p1->top--;
	p2->ator[p2->top - 1] = 0;
	p2->top--;
}
bool GetAnswer(Operand *p1, Operator *p2, char *expp)
{
	while (*expp||p2->top)
	{
		int n = 0;
		if (*expp == " ")//跳过空格
		{
			expp++;
			continue;
		}
		if (p2->top > p1->top)//表达式格式错误
			return false;
		if (isdigit(*expp))//压入操作数
		{
			while (*expp&&isdigit(*expp))
			{
				n = n * 10 + *expp-'0';//char型数字需要循环记录完整操作数
				expp++;
			}
			p1->and[p1->top] = n;
			p1->top++;
		}
		else if (*expp == '+' || *expp == '-' || *expp == '*' || *expp == '/')//压入操作符 || *expp == '(' || *expp == ')'
		{
			if (0 == p2->top)
			{
				p2->ator[p2->top] = *expp;
				p2->top++;
				expp++;
			}
			else
			{
				if (*expp == '+' || *expp == '-')//下一个运算符为+ - 出栈
				{
					Out(p1, p2);
				}
				else if (*expp == '*' || *expp == '/')
				{
					//+ - 压栈
					if (p2->ator[p2->top - 1] == '+' || p2->ator[p2->top - 1] == '-')
					{
						p2->ator[p2->top] = *expp;
						p2->top++;
						expp++;
					}
					// * / 出栈
					else if (p2->ator[p2->top - 1] == '*' || p2->ator[p2->top - 1] == '/')
					{
						Out(p1, p2);
					}
					else
						return false;
				}
			}
			//expp++;
		}
		else if (!(*expp)&&p2->top)
		{
			Out(p1, p2);
		}
		else
			return false;
	}
	if (1==(p1->top - 1) && !(p2->top - 1))
		return true;
	else
		return false;
}
int main()
{
	Operand oand;
	Operator oator;
	char exp[] = "1+2*3+-4*3-2*2+2";//5
	Init_Oper(&oand, &oator);
	GetAnswer(&oand, &oator, exp);
	printf("%s\n%d\n", exp, oand.and[oand.top-1]);
	system("pause");
	return 0;
}