C语言-用栈实现表达式求值(顺序栈)[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

函数目录：

1. 栈的基本操作：

• 创建栈并初始化（create）
• 入栈（push_in）
• 出栈（pop_out）
• 取栈顶元素（GetTop）

2. 优先级函数（Precede）
3. 求值函数（Operate）
4. 判断操作符函数（In）
5. 表达式求值函数（evaluateExpression）

其他：操作符栈（OPTR）,操作数栈（OPND）

谈谈我遇到的问题：

• 1.该选择数字栈还是字符栈？
  运算数是整型，而运算符是字符型，若选用字符栈，存入操作数时只能以‘0’–‘9’的字符形式存入，那么意味着无法存取两位以上的数字，也无法运算两位以上的数字，因为运算过程中的中间值超过两位也将无法转化成字符形态入栈计算，故用字符栈的局限性相当大，既不能输入超过0-9之间的数，还要同时保证操作数运算过程中也不能出现两位数。若选用数字栈（整型），能顺利地将任何数字存入栈中，而在存放操作符的时候，将会转化成ASCII码的形式存入栈中，故数字栈既可以存取多位数字，又能存取操作符，所以我选择的是数字栈。
• 2.若建立两个栈，一个数字栈用来存放运算数，一个字符栈用来存放操作符，是否可行？
  首先要肯定这是可行的！但是建立两个不同类型的栈，需要在代码中将栈的基本操作函数（建立，初始化，入栈，出栈，取栈顶元素）写两遍，然后在存取操作数和运算符的时候分别调用对应的操作，过程过于麻烦，代码也过于繁琐，不如数字栈来的简洁明了。
• 3.表达式输入方式的选取
  输入方式1：请输入表达式：3*（5-2）
  输入方式2：

请输入表达式：
3
*
（
5
—
2
）

第一种输入方式是直接打出表达式进行整体输入，而第二种则是以一个一个的方式读入，第一种输入方式可以直接建立一个数组char str[ ]然后用gets（str）进行输入，表达式输入非常直观。如果是第二种输入方式则是通过getchar（）进行一位位的读取，表达式输入不如第一种直观方便。

• 4.选择了以字符串的形式输入表达式后，表达式会如何存储？将如何访问？
  用gets（str）；或者scanf进行字符串读入表达式后，存储方式如下：
  
  多位数的存储方式：
  
  我们可以通过str[i]进行逐位的访问，通过i++；实现逐位的偏移，那么就可以写成str[i++]；需要注意的是多位数存储时，因为是将数字以字符形式存入字符数组中，所以只能一个单元格存一位数字。

• 5.存多位数时，一个单元格存一位数字，那我们如何将多位数正确的放入操作数栈中？
  在这里，处理多位数时，提出一种“归并”的思想，首先设一个int X1；用X1=str[i++]；读取每一位数字，再设一个int X2=0；通过X2=10*X2+X1；实现将已读取操作数归并到X2。那么我们现在的操作流程是，先读取第一位数字，放入X1，再放入X2，（第一次归并完成）然后继续让X1读取下一位字符，若X1读取的值仍是数字（可用isdigital判断X1是否为数字），则执行归并操作X2=10*X2+X1；（第二次归并操作完成），继续让X1读取下一位字符，若仍是数字，则继续归并（第三次归并完成）。由此往复，只要是下一位字符是数字，就归并一次。
  如34*5473的操作过程：X1读取3，归并至X2(第一次归并，此时X1=3;X2=3)，接着让X1读取4，识别到X1是数字，归并至X2（第二次归并，此时X1=4;X2=34）,发现下一位不是数字，停止读取，返回X2的值34，并入栈。此时我们就成功的用归并将34读取入栈 ，接下来再看4位的数5473如何读取，首先X1读取5，归并至X2(第一次归并，此时X1=5;X2=5)，接着让X1读取4，识别到X1是数字，归并至X2（第二次归并，此时X1=4;X2=54）,继续让X1读取7，归并至X2（第三次归并，此时X1=7;X2=547），继续让X1读取3，归并至X2（第三次归并，此时X1=3;X2=5473）,读取完成，返回X2的值5473，并入栈。

• 6.Precede优先级函数如何写？（算法63–95行）
  优先级函数以二维数组存储优先级表，用分支结构定位二维数组的行列坐标，这种写法看似繁琐实则简洁明了，直观！优先级函数也可以用逻辑式的写法，代码量虽少但是逻辑分析过程复杂，出错不好调试，维修成本过高，总的来说是一个可行的办法，但不是一个聪明的办法。

• 7.在运算除法时，若除数为0，如何给做出错误反馈？
  在Operate求值函数中，当theta是除号时，先用 if 判断如果除数为0，则返回错误结果，否则进行除法运算。

• 8.在检测到输入的字符是非法字符时如何给出错误反馈？在检测到输入字符是一个或多个空格时如何自动跳过空格？
  在evaluateExpression函数中，只需要添加两组与判断是否为运算符的if、判断是否为数字的if相平行的if来判断输入是否为空格，若为空格，则直接跳过读取下一位字符，若既不是数字，不是运算符，也不是空格，即为非法字符，返回错误提示。

注意：

1. 表达式的输入必须以“=”结束
   输入示例：3*（5-2）=
2. 输入格式可以有空格，但是唯一的BUG是在多位数的每一位之间加空格会出错！
3. isdigit是包含在头文件ctype.h中的判断是否为数字的函数，是数字返回1，不是返回0。
4. 此算法用于计算整型，若要计算浮点数，把相应的类型更换成double即可实现。
5. 算法运算逻辑是先以字符型读入字符数组中，再将字符型转换为整型存入数字栈中。

完整源代码

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h> 
#define Maxsize 100
typedef int dataType; 
typedef struct Stack
{ 

dataType *top;
dataType *base;
int stacksize;
}sqstack;
void create(sqstack *s)
{ 

s->base=(dataType *)malloc(Maxsize*sizeof(dataType)); 
if(!s->base)
{ 

printf("Space allocation failed!\n");
return;
}
s->top=s->base;
s->stacksize=Maxsize;
return;
}
int push_in(sqstack *s,dataType value)
{ 

if(s->top-s->base==s->stacksize)
{ 

printf("Stack is full!\n");
return;
}
*s->top=value; //"*s->top++=value;"
s->top++;
return;
}
int pop_out(sqstack *s,dataType *elem)
{ 

if(s->base==s->top)
{ 

printf("Stack is empty!");
return;
}
s->top--;
*elem=*s->top;  //"*elem=*--s->top;"
return;
}
dataType GetTop(sqstack *s) 
{ 

if(s->base==s->top)
{ 

printf("Stack is empty!\n");
printf("Unable to fetch top stack element!\n");
return;
} 
return *(s->top-1);
}
char Precede(char theta1,char theta2)
{ 

int i,j;
char pre[7][7]={ 
// + - * / ( ) = 
{ 
'>','>','<','<','<','>','>'},  
{ 
'>','>','<','<','<','>','>'},  
{ 
'>','>','>','>','<','>','>'},  
{ 
'>','>','>','>','<','>','>'},  
{ 
'<','<','<','<','<','=','0'},  
{ 
'>','>','>','>','0','>','>'},  
{ 
'<','<','<','<','<','0','='}}; 
switch(theta1){ 

case '+': i=0; break;  
case '-': i=1; break;  
case '*': i=2; break;  
case '/': i=3; break;  
case '(': i=4; break;  
case ')': i=5; break;
case '=': i=6; break;
}
switch(theta2){ 

case '+': j=0; break;  
case '-': j=1; break;  
case '*': j=2; break;  
case '/': j=3; break;  
case '(': j=4; break;  
case ')': j=5; break;
case '=': j=6; break;
}
return(pre[i][j]);
}
int Operate(int a,char theta,int b)
{ 

int result;
switch(theta){ 

case'+':return a+b;
case'-':return a-b;
case'*':return a*b;
case'/':             //判断除数是否为0，若除数为零返回错误提示 
if(b!=0)
return a/b;
else
{ 

printf("Divisor can not Be zero!\n");
exit(0);
}
}
}
int In(char c) //判断是否为运算符，是运算符返回1，若不是返回0
{ 

switch(c){ 

case '+':   
case '-':  
case '*':   
case '/':   
case '(':   
case ')': 
case '=': 
return 1;
default:
return 0;		   
}
}
int evaluateExpression(char exp[]) 
{ 

sqstack OPND,OPTR; //运算数栈、运算符栈
dataType a,b,theta,x,X1,X2;  /* a，b，theta用于Operate函数 X用于存放多余的出栈字符 X1,X2用于归并 */
char ch; //读取字符的变量
int i=0; //指向存放表达式数组的下标指针（其实不是真正的指针，而是数组下标）
create(&OPND); //建立并初始化运算数栈OPND
create(&OPTR); //建立并初始化运算符栈OPTR
push_in(&OPTR,'='); //先将“=”号压入OPTR栈（表达式也必须以“=”结束）
ch=exp[i++]; //ch读取字符数组第一个元素，并将指针i后移一位
while(ch!='='||GetTop(&OPTR)!='=') //表达式没有扫描完毕或OPTR的栈顶不为“=”
{ 

if(In(ch)) //判断ch是否为操作符
{ 

switch(Precede(GetTop(&OPTR),ch))//比较ch的与OPTR栈顶元素的优先级
{ 

case'<':
push_in(&OPTR,ch);
ch=exp[i++]; //读取下一位字符并将指针向后偏移一位
break;
case'>':
pop_out(&OPTR,&theta); 
pop_out(&OPND,&b);
pop_out(&OPND,&a);
push_in(&OPND,Operate(a,theta,b));
break;
case'=':
pop_out(&OPTR,&x);
ch=exp[i++]; //读取下一位字符并将指针向后偏移一位
break;
}
}
else if(isdigit(ch)) //判断是否为数字
{ 

X1=ch-'0'; //将字符形式转化为数字
push_in(&OPND,X1);
X2=X1;
ch=exp[i++]; //读取下一位字符并将指针向后偏移一位
while(isdigit(ch)) //判断下一位是否还是数字
{ 

X1=ch-'0';
X2=10*X2+X1; //归并至X2
pop_out(&OPND,&x);
push_in(&OPND,X2);
ch=exp[i++]; //读取下一位字符并将指针向后偏移一位
} 
} 
else if(ch==' ') //判断是否为空格
{ 

while(ch==' ') //跳过若干个空格
{ 

ch=exp[i++]; //忽略空格，直接取下一位
}
}
else //若不是上述三种情况之一，则为非法字符
{ 

printf("Input has illegal characters!\n");
printf("Please enter again.\n");
exit(0); //返回错误提示
}
}
return(GetTop(&OPND)); //最后返回操作数栈顶为运算结果
}
int main()
{ 

char exp[100]; //定义一个字符数组用于存储表达式
int result;
printf("Please Enter Expression:");
gets(exp); //换成scanf（“%s”，exp）；也可以
result=evaluateExpression(exp);
printf("\n");
printf("%s%d\n",exp,result);
return 0;
}

执行结果：

参考：

1. 数据结构（C语言第二版）——严蔚敏
2. 栈的经典应用——yuluows
3. 栈的应用（表达式求值）——Sup_klz