【数据结构】【线性表】栈在算术表达式中的应用
前言
栈如何在算术表达式中应用？
中缀表达式如何转为后缀表达式？
只会算四则运算？
带函数等的高阶算术表达式如何运算？
通过本篇内容，我们解决一个看起来简单其实比较复杂的算术表达式的计算，区别于其它只讲述了四则运算的文章，本篇文章更加注重实用性，可计算函数，指数等，拓展性强，可根据需求设计计算指数，乘方甚至虚数等。
需要注意的是该文章更加注重作者解决该问题的过程，更加注重解决算术表达式的计算问题，有一定理解难度，需要对线性表，栈，结构体，枚举等有一定了解。
文章脉络
大部分文章告诉我们的算术表达式的计算步骤是
本篇前半部分主要解释为什么是这样一个步骤？后半部分主要解释实际应用中的细节？对于只想知道方法的读者可自行跳到后半部分。
为什么要将中缀表达式转换成后缀表达式？
要想解释为什么要抛弃我们常用的中缀表达式而采用后缀表达式去计算算术表达式，这需要我们从中缀表达式本身去找问题。
常规思路解决算术表达式的困境
常规思路解决算术表达式的计算会有一个很明显的特征——混乱！
我们先来看一个简单的公式：
什么都不用多说，写程序，怎么处理？动动脑子，用程序怎么解决这个问题，有思路嘛？
在代码中，怎么处理括号？优先级怎么区分？5-3、4/2这种加减乘除的运算中间是运算符，两边是操作数，但如果是sin、cos这些函数其表达式却是前面为运算符，后面是操作数。你怎么处理？
把思路逻辑写下来，自己去写一下程序，看看你怎么办。就光括号和加减乘除的优先级区分就够我们喝一壶了。觉得自己行的自己写一下，嵌套括号和运算符之间的优先级怎么做区分？一写一个不吱声，为什么会这样？你们自己写了的同学就会感觉到一个问题--混乱
导致混乱的原因是：
- 括号难以处理，导致括号的优先级和加减乘除的优先级混在一起
- 运算混乱，主要体现在遍历表达式的过程中，指针来回走动。
例如5-3，扫描到运算符- 时，指针要前后移动取- 两边的操作数。
重新审视括号
我们进一步思考括号，它的作用和运算符很像但又不一样，像是因为可以划分优先级，不像是因为它只划分不计算，计算需要依靠括号里面的表达式。也就是说，括号里面是有可能还有表达式的。那么我们是不是可以认为括号只是一个切割表达式的作用呢？而优先级的改变是不是可以视为，表达式所在位置的顺序改变。
因此我们需要将原有的表达式变成一个不需要括号，同时也能无歧义的表达原有表达式计算顺序的新表达式。
常规思路需要解决的两个问题
- 括号的处理
- 表达式优先级及运算符的处理
打破困境
括号的处理
我们现在暂时抛开表达式的运算符和操作数，直接看括号：
我们先看一下有多少个完整的括号：
我们可以看到的是这里一共有五对括号。我们观察会得到两种处理方式：
- 1->3->5->4->2.
- 5->4->3>2->1.
我们可以看到的是两种顺序都是可以的，首先第一种的思路是得到一个完整的括号处理一个括号；第二种的思路是从最里层到最外层依次处理。第二种往往是我们人相对更喜欢的方法，但区分里层和外层本身也是一个值得探讨的问题。
我们再次回到第一个方法：遇到一个完整的括号就处理一个括号，该如何实现呢？
我们先观察一下从中找到特点，如果有同学觉得这里乱的，我们不妨用归纳法去找，归纳法的步骤是：
- 找典型特例
- 总结特例规则
- 映射到所有情况
- 证明规则
好的，我们先创建一个多重括号的特例：
在这特例中我们需要先处理顺序是5->4->3->2->1，如果还是看不出来，那么我们再切一半，就看左边藏青色部分，最后的括号最先处理，最开始得到括号最后处理。这个规则是不是很符合我们栈的规则，先进后出，后进先出。
在这里我们可以得出一条结论，对于多重括号来说，均有先进后出的特点，可以通过栈来实现括号匹配。
将结论推广，用栈可以实现括号匹配。进栈条件：左括号；出栈条件：遇到右括号
验证：
1.建立空栈：
2.遇到左括号，入栈：
3.遇到右括号，出栈
4.遇到左括号，入栈
5.遇到左括号，入栈：
6.遇到右括号，出栈
后面的都是重复这个过程，我们在这里不再赘述了，可以证明的是，栈可以非常简单的处理其括号匹配问题。
表达式中运算符及操作数的处理
首先我们回到公式本身：
我们将公式的各个符号进行分类，主要分为以下三类：
- 操作数：具体数字
- 运算符：加减乘除等运算符号
- 界限符：各类括号等表示界限的符号
前缀表达式和后缀表达式
在我最开始自己设计的时候，把括号当成了最高级的运算符，其实这是错的。严格来说括号不属于运算符，但它却有分割表达式或改变运算优先级的作用。同时括号也是很难处理的，很久以前的波兰数学家就有一个想法：可不可以不要界限符，但也要无歧义的表达计算顺序？也是因为这个思想，诞生了两个很重要的表达式格式：
- 波兰式，即前缀表达式；
- 逆波兰式，即后缀表达式
我们先来看一下前缀、后缀以及我们常用的中缀表达式的格式：
- 中缀表达式：运算符在两个操作数中间
- 前缀表达式：运算符在两个操作数前面
- 后缀表达式：运算符在两个操作数后面
我们可以看到的是，在中缀表达式转换成前缀或者后缀表达式后，表达式中没有了括号，同时顺序重新排列已经将优先级分好了。
选择前缀表达式还是后缀表达式？
以5+(4-2)*1为例。上面讲到将中缀表达式转变为前缀表达式或者后缀表达式，对于二者的选用其实无所谓，但我们习惯性选后缀是因为后缀表达式的计算顺序是从左往右的符合一般人的习惯；而前缀表达式是从右往左的。
后缀表达式的计算
如何处理后缀表达式呢？从左往右看，遇到运算符就将前面的两个数字提取出来运算，结果为新的数，一直到表达式处理完。
为了避免我们指针的来回走动，我们用栈来实现这个功能：
- 从左往右扫描后缀表达式各个元素直到处理完所有元素。
- 如果是操作数直接入栈
- 如果是运算符，弹出两个栈顶元素执行运算，结果压回栈顶
- 所有元素处理完的栈顶元素即为运算结果
例如：计算5-(4-2)*1 ，将其转换为后缀表达式之后进行处理
5是操作符，入栈
4是操作符，入栈
2是操作符，入栈
-是运算符，出栈两个进行操作符运算
结果入栈
1是操作数人、，入栈
*是运算符 出栈两个进行运算
结果入栈
+是操作符，出栈两个进行运算
结果入栈
到这里一切都似乎很圆满，但自己独立写过算术表达式计算程序的人就会发现，这里有坑，巨大的坑。
实际操作
算术表达式的数据类型的讨论
我们发现，用后续表达式去表达中缀表达式，即解决了括号的问题，也解决了优先级的问题；同时后缀表达式的计算也非常简单。
因此我们主要解决将中缀表达式转变为后缀表达式的问题。
当各位兴致勃勃觉得问题马上就要解决的时候，其实很多人不知道前面有一个大坑。
这个大坑就是算术表达式的数据类型，比如20+5这个表达式，是整数还是小数或者是字符呢？很显然字符才可以表示这个表达式，但另一个问题是既然是字符，那么20+5在这里没有数学意义，只是作为符号，例如这里的20，在储存中是字符'2'和'0'的ASIIC码，并不是20这个数字，他们是分隔的，看起来是20但表示数字20而是两个字符，字符没有直接计算意义，而且字符不能乘除。
因此我们应该将公式用什么数据类型表示呢？我们先看一下一个公式里有什么？
- cos ln为函数
- （ ）界限符
- 5 3为数值
- + -为操作符
- 特殊常数
因此算术表达式字符有多含义，单一的数据类型显然不能够很好的表示算术表达式；同时我们发现在不考虑实际含义的情况下也可以分为数值和字符两个类型。
我们最好还是用线性表去表示算术表达式；这里也没有内存什么的特殊限制，因此我们直接定义一个顺序线性表去用于算术表达式。其表达式线性表的结构是：
线性表每个元素的结构为
中缀表达式转后缀表达式的具体步骤
- 分配一个栈stack和线性表ll
- 从在中序表达式从左往右逐个取字符str
- 如果str是数字，读取整个数字，转化为浮点数并插入到ll后
- 如果str是符号：
- str是'(',直接压入栈
- str是')',将距离栈顶最近的'('之前的所有运算符逐个出栈并插入到ll后，"()"抛弃
- str为'-'，判断是否是字符串第一个字符或者栈顶为'('，如果是则将后续的数字取反，'-'号抛弃
- str为字符常量，如圆周率Π和自然对数e，转换为数值直接插入ll后
- str为函数，sin、cos、tan等，以数字的形式插入ll再插入f作为标识
- str为运算符，如果栈顶是‘('则直接压入栈；如果栈顶不是'('则比较优先级，高进底出
计算后缀表达式实际操作
操作思路和上述思路一致，但因为引入了函数，因此实际操作有些许变化
- 从左往右扫描后缀表达式各个元素直到处理完所有元素。
- 如果是操作数直接入栈
- 如果是运算符
- 运算符是函数f：弹出1个栈顶元素执行函数运算，结果压回栈顶
- 运算符不是函数f：弹出2个栈顶元素执行运算，结果压回栈顶
- 所有元素处理完的栈顶元素即为运算结果
源码
count.h文件
#ifndef _COUNT_H
#define _COUNT_H
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#include <float.h>
#define E 2.7
#define MaxSize 20
//元素数据
typedef struct Type{
float num;
char str;
}Type;
//元素属性标记
typedef enum{
NUMVALUE,//操作数
OPERATOR,//运算符
CONST_NUM,//常数
FUNCTION,//函数
LIMIT,//界限符
INVALID_Type//数据类型无效
}TypeFlag;
//常数标记
typedef enum{
E_FLAG, //自然对数标志
PI_FLAG, //π标志
NO_CONST //非常数
}CONST_FLAG;
//函数标记
typedef enum{
LN_FLAG,
LOG_FLAG,
SIN_FLAG,
COS_FLAG,
TAN_FLAG,
ABS_FLAG,
SINH_FLAG,
COSH_FLAG,
TANH_FLAG,
ASIN_FLAG,
ACOS_FLAG,
ATAN_FLAG,
FUNC_INVALID //函数不合法
}FUNC_FLAG;
//顺序表元素结构体
typedef struct LLElem{
TypeFlag elemtype;
Type elemValue;
}LLElem;
//顺序表结构体
typedef struct{
LLElem ll[MaxSize];
int length;
}SeqList;
// 初始化线性表
void InitList(SeqList *L) {
for (int i = 0; i < MaxSize; i++) {
L->ll[i].elemtype = INVALID_Type; // 初始化所有元素为无效类型
}
L->length = 0; // 初始长度为0
}
//在顺序表L的结尾插入元素e
bool ListInsert(SeqList *L,LLElem e){
if(L->length>MaxSize-1) //判断当前空间是否满了，满了则不能插入
return false; //空间已满，插入失败
L->length++; //顺序表长度+1
L->ll[L->length-1]=e; //在结尾位置插入元素e
return true;//插入成功
}
//线性符号栈结构体
typedef struct {
char str[MaxSize];
int top;
}SqStack;
//线性运算栈结构体
typedef struct {
LLElem elem[MaxSize];
int top;
}CountStack;
//初始化计算栈
void InitCountStack(CountStack *S){
S->top=-1;
}
//计算栈入栈
bool PushCountStack(CountStack *S,LLElem e){
if(S->top==MaxSize-1)//判断顺序栈是否满员
return false;//顺序栈已满，进栈失败
S->top=S->top+1;//栈顶指针先+1
S->elem[S->top]=e;//元素进栈
return true;//进栈成功
}
//计算栈出栈
bool PopCountStack(CountStack *S,LLElem *e){
if(S->top==-1)//判断是否空栈
return false;//空栈，出栈失败
*e=S->elem[S->top];//数据出栈
S->top--;//栈顶指针-1
return true;//出栈成功
}
//计算栈读栈顶元素值
LLElem ReadCountTOP(CountStack *S){
LLElem e;
e=S->elem[S->top];//读取栈顶数据
return e;//读栈顶成功
}
/*优先级标记*/
typedef enum{
LEVEL_INVALID, //算符不合法
LEVEL_SMALLER, //优先级低
LEVEL_SAME, //优先级相等
LEVEL_BIGGER //优先级高
}LEVEL_TYPE;
#endifcount.c文件
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#include <float.h>
#include <count.h>
// 将字符串转换为浮点数的函数
float string_float(char *str) {
// 如果输入为空或空字符串，返回0.0f
if (str == NULL || *str == '\0') {
return 0.0f;
}
// 初始化变量
float num = 0.0f; // 最终结果
int i = 0; // 当前字符索引
int flag = 1; // 符号标志，1表示正数，-1表示负数
int numflag=0;
int fractional_part = 0; // 是否处理小数部分的标志
float fractional_divisor = 1.0f; // 小数部分的除数
// 检查负号
if (str[i] == '-') {
flag = -1;
i++;
}
// 转换数字部分和小数部分
while (str[i] != '\0') {
if (str[i] >= '0' && str[i] <= '9') {
numflag=1;
int digit = str[i] - '0'; // 将字符转换为数字
if (fractional_part) {
// 处理小数部分
fractional_divisor *= 10.0f;
num += digit / fractional_divisor;
} else {
// 处理整数部分
if (num > (FLT_MAX - digit) / 10.0f) {
// 发生溢出，返回0或其他错误值
return 0.0f;
}
num = num * 10.0f + digit;
}
} else if (str[i] == '.' && !fractional_part) {
// 遇到小数点，开始处理小数部分
fractional_part = 1;
} else if(numflag==1){
// 非法字符，直接返回当前结果
break;
}
i++;
}
// 返回最终结果，考虑符号
return flag * num;
}
//常数标记
CONST_FLAG const_flag(char c)
{
switch(c)
{
case 'e' : return E_FLAG;
}
return NO_CONST;
}
//函数字符串标记
TypeFlag StringFlag(char c){
if (c == '+' ||
c == '-' ||
c == '*' ||
c == '/' ||
c == '^'
)
{
return OPERATOR;
}
else if((c>='0' && c<='9') || c=='.')
{
return NUMVALUE;
}
else if(const_flag(c) != NO_CONST) //若为常数
{
return CONST_NUM;
}
else if(c == 'l' || c == 's' || c == 'c' || c == 't' || c == 'a') //首字母是s,c,t,l，则判定为函数
{
return FUNCTION;
}
else
{
return INVALID_Type;
}
}
/*求字符串S的长度*/
int StrLength(char *S){
int len=0;
while(S[len]!='\0'){
len++;
}
return len;
}
/*比较字符串*/
int Strcompare(char *str1,char *str2){
int len1=StrLength(str1),len2=StrLength(str2);
for(int i=0;i<len1 && i<len2;i++){
if(str1[i]!=str2[i])
return str1[i]-str2[i];
}
return len1-len2;
}
//函数类型标记
FUNC_FLAG FunFalg(char *p) {
char s[4]; // 需要多一个字节来存储终止符 '\0'
for (int i = 0; i < 3; i++) {
s[i] = p[i];
}
s[3] = '\0'; // 确保字符串以 '\0' 结尾
if (Strcompare(s, "sin") == 0) {
return SIN_FLAG;
}
else if(Strcompare(s, "cos") == 0) {
return COS_FLAG;
}
else if(Strcompare(s, "ln") == 0) {
return LN_FLAG;
}
else {
return FUNC_INVALID;
}
}
/*优先级判断*/
LEVEL_TYPE Priority(char s,char p){
char operator1_level, operator2_level;
//判断两个操作符在两个优先级表中的位置
switch(s)
{
case '+' :
case '-' : operator1_level = 1; break;
case '*' :
case '/' : operator1_level = 2; break;
default : return LEVEL_INVALID;
}
switch(p)
{
case '+' :
case '-' : operator2_level = 1; break;
case '*' :
case '/' : operator2_level = 2; break;
default : return LEVEL_INVALID;
}
//判断两个操作符的优先级关系
if((operator1_level - operator2_level) > 0)
{
return LEVEL_BIGGER;
}
else if((operator1_level - operator2_level) < 0)
{
return LEVEL_SMALLER;
}
else
{
return LEVEL_SAME;
}
}
SeqList *zhong_hou(char *s){
CountStack stack;//新建栈
SeqList *ll= (SeqList*)malloc(sizeof(SeqList));//新建顺序表用于储存后缀表达式
int p=0;//当前字符位置
int numflag=0;
int funflag=0;
char temp;//出栈临时储存字符
LLElem ElemType;//临时顺序表元素
InitCountStack(&stack);//初始化顺序栈
InitList(ll);//初始化顺序表
while(s[p]!='\0'){
if(StringFlag(s[p])==NUMVALUE){//该字符为数字
funflag=0;
if(numflag==0){
numflag=1;
//将字符串转化为float插入顺序表
ElemType.elemtype=NUMVALUE;//标记该元素属性是操作数
ElemType.elemValue.num=string_float(s+p);//转换成float并记录
ElemType.elemValue.str='\0';//将元素的符号属性设置成结束符
ListInsert(ll,ElemType);//将该元素插入线性表
}
}
else if(s[p]=='('){
numflag=0;
if(funflag==1){
funflag=0;
PushCountStack(&stack,ElemType);//将该元素插入线性表
}
ElemType.elemtype=LIMIT;
ElemType.elemValue.num=0;
ElemType.elemValue.str='(';//将元素的符号属性设置成结束符
PushCountStack(&stack,ElemType);//直接压入栈
}
else if(s[p]==')'){
numflag=0;
funflag=0;
//距离栈顶最近的 ( 之前符号的全部出栈
do {
PopCountStack(&stack, &ElemType);//取出栈顶元素
if (ElemType.elemValue.str != '(') {
ListInsert(ll, ElemType);//将该元素插入线性表
}
}while(temp!='(' && stack.top!=-1);
}
else if((s[p]=='-') && ((s[p+1]>='0' && s[p+1]<='9')&&(s[p-1]=='('))){
funflag=0;
if(numflag==0){
numflag=1;
//将字符串转化为float插入顺序表
ElemType.elemtype=NUMVALUE;//标记该元素属性是操作数
ElemType.elemValue.num=string_float(s+p);//转换成float并记录
ElemType.elemValue.str='\0';//将元素的符号属性设置成结束符
ListInsert(ll,ElemType);//将该元素插入线性表
}
}
else if(StringFlag(s[p])==CONST_NUM){
funflag=0;
numflag=1;
//将字符串转化为float插入顺序表
ElemType.elemtype=NUMVALUE;//标记该元素属性是操作数
ElemType.elemValue.num=E;//转换成float并记录
ElemType.elemValue.str='\0';//将元素的符号属性设置成结束符
ListInsert(ll,ElemType);//将该元素插入线性表
}
else if(StringFlag(s[p])==FUNCTION){
numflag=0;
if(funflag==0)
{
funflag=1;
ElemType.elemtype=FUNCTION;//标记该元素属性是操作数
ElemType.elemValue.num=FunFalg(s+p);//转换成函数标记并记录
ElemType.elemValue.str='f';//将元素的符号属性设置成结束符
}
}
else if(StringFlag(s[p])==OPERATOR){
numflag=0;
funflag=0;
if(ReadCountTOP(&stack).elemValue.str=='('){
ElemType.elemtype=OPERATOR;
ElemType.elemValue.num=0;
ElemType.elemValue.str=s[p];//记录元素操作符
PushCountStack(&stack,ElemType);//直接压入栈
}
else if(stack.top>=0){
while (Priority(ReadCountTOP(&stack).elemValue.str,s[p] ) == LEVEL_BIGGER
||Priority(ReadCountTOP(&stack).elemValue.str,s[p]) == LEVEL_SAME) {
PopCountStack(&stack, &ElemType); // 弹出栈顶操作符并插入顺序表
ListInsert(ll, ElemType); // 将该元素插入线性表
if(ReadCountTOP(&stack).elemValue.str=='('||stack.top<=0)
break;
}
ElemType.elemtype=OPERATOR;
ElemType.elemValue.num=0;
ElemType.elemValue.str=s[p];//记录元素操作符
PushCountStack(&stack,ElemType);//直接压入栈
}
else{
ElemType.elemtype=OPERATOR;
ElemType.elemValue.num=0;
ElemType.elemValue.str=s[p];//记录元素操作符
PushCountStack(&stack,ElemType);//直接压入栈
}
}
p++;
}
while(stack.top>=0){
PopCountStack(&stack, &ElemType); // 弹出栈顶操作符并插入顺序表
ListInsert(ll, ElemType); // 将该元素插入线性表
}
return ll;
}
float CountHou(SeqList L){
CountStack stack;//新建计算栈
float val1,val2;
LLElem Elem;
InitCountStack(&stack);
for(int i=0;i<L.length;i++){
if(L.ll[i].elemtype==NUMVALUE){
PushCountStack(&stack,L.ll[i]);
}
else if(L.ll[i].elemtype==OPERATOR){
PopCountStack(&stack,&Elem);
val2=Elem.elemValue.num;
PopCountStack(&stack,&Elem);
val1=Elem.elemValue.num;
switch(L.ll[i].elemValue.str){
case '+':
Elem.elemValue.num=val1+val2;
break;
case '-':
Elem.elemValue.num=val1-val2;
break;
case '*':
Elem.elemValue.num=val1*val2;
break;
case '/':
Elem.elemValue.num=val1/val2;
break;
}
Elem.elemtype=NUMVALUE;
PushCountStack(&stack,Elem);
}
else if(L.ll[i].elemtype==FUNCTION){
PopCountStack(&stack,&Elem);
val1=Elem.elemValue.num;
switch((int)L.ll[i].elemValue.num){
case LN_FLAG:
Elem.elemValue.num=ln(val1);
break;
case SIN_FLAG:
Elem.elemValue.num=sin(val1);
break;
case COS_FLAG:
Elem.elemValue.num=cos(val1);
break;
}
Elem.elemtype=NUMVALUE;
PushCountStack(&stack,Elem);
}
}
return ReadCountTOP(&stack).elemValue.num;
}
int main() {
char *s="(cos(3-3)+1)/2";
SeqList *ll=zhong_hou(s);
float value=CountHou(*ll);
printf("\n");
printf("%d ",ll->length);
for (int i = 0; i < ll->length; i++) {
if (ll->ll[i].elemtype == NUMVALUE) {
printf("%f ", ll->ll[i].elemValue.num);
} else {
printf("%c ", ll->ll[i].elemValue.str);
}
}
printf("\n");
printf("\t%f ",value);
free(ll); // 释放顺序表的内存
return 0;
}
【注意】上述代码中字符串有关代码可以直接引用string.h头文件，使用其中的库函数，作者在这里是为了验证自己写的字符串相关函数的实用性，读者不需要掌握。
总结
算术表达式的计算在实际应用中其实比我们想象中复杂的多，我们需要知道的是，后缀表达式在解决这个问题中的优越性，复杂的算术表达式也和四则运算在思路是没有太大区别。
我们要掌握如何正确的将中序表达式转换为后缀表达式，线性表的结构创建是一个关键。
该篇文章作者改了很多版本，但无论怎样都无法清楚的讲清楚其内在逻辑，一方面是作者表达能力有限，另一方面在作者看来，唯有真正去做了这个事的人才能感受到其中的魅力所在，创建这篇文章的初衷也是看到该平台上只有四则运算的处理，想起了当初自己孤立无援的横冲直撞的样子，希望该篇文章对另一个我有所启发。