栈的应用--计算器实现四则运算

学习一个知识点并不是那么难，而要运用所学的知识点去实现一个功能或者做一个项目却总不是那么简单。就像这个标题，如何用栈来做出一个计算器呢？

我们先来思考一番，比如有个式子：9 + （3 - 1） * 3 + 10 / 2 ， 遇到这个式子我们可能一气呵成就能写出答案是20，因为我们从小学就开始学习数学然后计算，我们太习惯了去做这件事而忘记了去思考为什么要这么做。我们先放慢100倍我们的脑速，第一步，我们直接锁定了括弧，然后乘除，最后是加减，没错，我们考虑了优先级，然后，除了运算符，剩下的就是数字了。那么，这些跟栈有什么关系呢？我们是不是可以设置两个栈，一个用来放数字，另一个用来放运算符（操作符），但是，一个正常的式子都是一个数字然后一个运算符，交替着组成一个式子，这样表示方式叫做中缀表达式。如果我们按从左到右的顺序来分别安放数字和运算符，那么优先级不就完全被打乱么。可见这样是行不通的。

所以，我们要引入一种不需要括号的后缀表达式，叫做逆波兰（RPN）表示。接着这个栗子来说，如果用后缀表达式应该为：“9 3 1 - 3 * + 10 2  / +” ，顾名思义就是所有的符号都要在运算数字的后面了。

怎么将中缀表达式转为后缀表达式呢？

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，若是右括号或优先级低于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

是不是已经晕了。我们就拿刚才的栗子强行分析一波。直接将中缀转后缀以及对后缀的计算于一体，简单粗暴。

接下来我们用语言来把上面的思路表达出来：

#include <stdio.h>
#include <stdlib.h>

#define OK       1000
#define ERROR	 2000

/* 定义结点结构体 */
struct node
{
	int data;
	struct node *next;
};
typedef struct node Node;

/* 定义栈结构体 */
struct stack
{
	Node *top;
	int count;
};
typedef struct stack Stack;

/* 初始化栈 */
int InitStack(Stack *S)
{
	S->top = NULL;
	S->count = 0;

	return OK;
}

/* 判断栈空 */
int EmptyStack(Stack *S)
{
	return (S->count == 0) ? OK : ERROR;
}

/* 进栈 */
int Push(Stack *S, int e)
{
	Node *p = (Node *)malloc(sizeof(Node));
	if(p == NULL)
	{
		return ERROR;
	}
	p->data = e;
	p->next = S->top;
	S->top = p;
	S->count++;

	return OK;
}

/* 获取栈顶 */
int GetTop(Stack *S)
{
	if(NULL == S->top)
		return ERROR;

	return (S->top->data);
}

/* 自定义优先级 */
int Priority(char s)
{
	switch(s)
	{
		case '(':				//括号优先级最高
			return 3;
		case '*':
		case '/':				//乘除次之
			return 2;
		case '+':
		case '-':				//加减最低
			return 1; 
		default :
			return 0;
	}
}

/* 出栈 */
int Pop(Stack *S)
{
	int e;

	if (NULL == S->top)
		return ERROR;

	Node *p = S->top;
	e = p->data;
	S->top = p->next;
	free(p);
	S->count--;

	return e;
}

int main()
{
	Stack num, opt;
	char str[100] = {0};
	int i = 0, tmp = 0, j;

	if (InitStack(&num) != OK || InitStack(&opt) !=OK)
	{
		printf("Init Failure!\n");
		exit(1);
	}

	printf("Please input operator :\n");
	scanf("%s", str);

	while (str[i] != '\0' || EmptyStack(&opt) != OK)
	{
		if(str[i] >= '0' && str[i] <= '9')
		{
			tmp = tmp *10 + str[i] -'0';
			i++;
			if(str[i] < '0' || str[i] > '9')
			{
				Push(&num, tmp);
				tmp = 0;
			}
		}
		else
		{
			//进栈不运算
			if((EmptyStack(&opt) == OK) || (GetTop(&opt) == '(' && str[i] != ')') ||
			Priority(str[i]) > Priority(GetTop(&opt))) 
			{
				Push(&opt, str[i]);
				i++;
				continue;
			}

			//出栈不运算
			if (GetTop(&opt) == '(' && str[i] == ')')
			{
				Pop(&opt);
				i++;
				continue;
			}

			//出栈运算
			if ((str[i] != '\0' && EmptyStack(&opt) != OK) || (str[i] == ')' && GetTop(&opt)!= '(') || 
			Priority(str[i]) <= Priority(GetTop(&opt)))
			{
				switch (Pop(&opt))
				{
					case '+':
						Push(&num, Pop(&num) + Pop(&num));
						break;
					case '-':
						j = Pop(&num);
						Push(&num, Pop(&num) - j);
						break;
					case '*':
						Push(&num, Pop(&num) * Pop(&num));
						break;
					case '/':
						j = Pop(&num);
						Push(&num, Pop(&num) / j);
						break;
				}
				continue;
			}
		}
	}
	printf("result is:%d\n",Pop(&num));

}