堆栈应用－后缀式四则计算器

核心提示：本计算器利用堆栈来实现，1、定义后缀式计算器的堆栈结构 因为需要存储的单元不多，堆栈应用－后缀式四则计算器，这里使用顺序栈，即用一维数组来模拟堆栈：#define MAX 100int stack[MAX];int top=0; 因此程序中定义了长度为MAX的一维数组，完整的程序代码如下：#include<s

　　本计算器利用堆栈来实现。
1、定义后缀式计算器的堆栈结构
　  因为需要存储的单元不多，这里使用顺序栈，即用一维数组来模拟堆栈：
#define MAX 100
int stack[MAX];
int top=0;
　  因此程序中定义了长度为MAX的一维数组，这里MAX用宏定义为常数100，我们可以修改宏定义而重新定义堆栈的大小。
　  整型数据top为栈顶指示，由于程序开始时堆栈中并无任何数据元素，因此top被初始化为0。
2、存储后缀式计算器的运算数
　　我们定义了堆栈stack[MAX]后，就可以利用入栈操作存储先后输入的两个运算数。
下面看一下是如何实现的：
int push(int i)　　　　/*存储运算数，入栈操作*/
{
　　if(top<MAX)
　　{
　　　　stack[++top]=i;　　/*堆栈仍有空间，栈顶指示上移一个位置*/
　　　　return 0;
　　}
　　else　　　　　　　　/*堆栈已满，给出错误信息，返回出错指示*/
　　{
　　　　PRintf("The stack is full");
　　　　return ERR;
　　}
}
　　我们在调用函数push时，假如它的返回值为0，说明入栈操作成功；否则，若返回值为ERR(在程序中说明为-1)，说明入栈操作失败。
3、从堆栈中取出运算数
　　当程序中读完了四则运算符后，我们就可以从堆栈中取出已经存入的两个运算数，构成表达式，计算出结果。取出运算数的函数采用的正是出栈算法。在本例中，实现该算法的函数 为pop():
int pop();　　　　/*取出运算数，出栈操作*/
{
　　int var;　　　/*定义待返回的栈顶元素*/
　　if(top!=NULL)　 /*堆栈中仍有数据元素*/
　　{
　　　　var=stack[top--];　　/*堆栈指示下移一个位置*/
　　　　return var;
　　}
　　else　　　　/*堆栈为空，给出错误信息，并返回出错返回值*/
　　　　printf("The stack is cmpty!\n");
　　return ERR;
}
　　同样，假如堆栈不为空，pop()函数返回堆栈顶端的数据元素，否则，给出栈空提示，并返回错误返回值ERR。
4、设计完整的后缀式计算器
　　有了堆栈存储运算数，后缀式计算器的设计就很简单了。程序首先提示用户输入第一个运算数，调用push()函数存入堆栈中；而后提示用户输入第二个运算数，同样调用push()函数存入堆栈中。接下来，程序提示用户输入+,-,*,/四种运算符的一种，程序通过switch_case结构判定输入运算符的种类，转而执行不同的处理代码。以除法为例，说明程序的执行流程：
　　　　case '/':
　　　　　　b=pop();
　　　　　　a=pop();
　　　　　　c=a/b;
　　　　　　printf("\n\nThe result is %d\n",c);
　　　　　　printf("\n");
　　　　　　break;
　　程序判定用户输入的是除号后，就执行上述代码。首先接连两次调用pop()函数从堆栈中读出先前输入的运算数，存入整型数a和b中；然后执行除法运算，结果存入单元c中。这时需要考虑究竟谁是被除数，谁是除数。由于开始我们先将被除数入栈，根据堆栈“先进后出”的原则，被除数应该是第二次调用pop()函数得到的返回值。而除数则是第一次调用pop()函数得到的返回值。
　　最后程序打印出运算结果，并示提示用户是否继续运行程序：
printf("\t Continue?(y/n):");
l=getche();
if(l=='n')
　　exit(0);
　　假如用户回答是"n"，那么结束程序，否则继续循环。

完整的程序代码如下：
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define ERR -1
#define MAX 100　　　　/*定义堆栈的大小*/
int stack[MAX];　　　　/*用一维数组定义堆栈*/
int top=0;　　　　　　/*定义堆栈指示*/

int push(int i)　　　　/*存储运算数,入栈操作*/
{
　　if(top<MAX)
　　{
　　　　stack[++top]=i;　　/*堆栈仍有空间，栈顶指示上移一个位置*/
　　　　return 0;
　　}
　　else
　　{
　　　　printf("The stack is full");
　　　　return ERR;
　　}
}
int pop()　　　　/*取出运算数，出栈操作*/
{
　　int var;　　　　/*定义待返回的栈顶元素*/
　　if(top!=NULL)　　/*堆栈中仍有元素*/
　　{
　　　　var=stack[top--];　　/*堆栈指示下移一个位置*/
　　　　return var;　　　　/*返回栈顶元素*/
　　}
　　else
　　　　printf("The stack is empty!\n");
　　return ERR;
}
void main()
{
　　int m,n;
　  char l;
　　int a,b,c;
　　int k;
　　do{
　　　　printf("\tAriothmatic Operate simulator\n");　　/*给出提示信息*/
　　　　printf("\n\tPlease input first number:");　　  /*输入第一个运算数*/
　　　　scanf("%d",&m);
　　　　push(m);　　　　　　/*第一个运算数入栈*/
　　　　printf("\n\tPlease input second number:");　　/*输入第二个运算数*/
　　　　scanf("%d",&n);
　　　　push(n);　　　　　　/*第二个运算数入栈*/
　　　　printf("\n\tChoose operator(+/-/*//):");
　　　　l=getche();　　　　 /*输入运算符*/
　　　　switch(l)　　　　　　/*判定运算符，转而执行相应代码*/
　　　　{
　　　　　　case '+':
　　　　　　　　b=pop();
　　　　　　　　a=pop();
　　　　　　　　c=a+b;