-
【表达式求值】
前言
朋友们大家好，前段时间熊猫我学习了栈的相关知识，通过做题发现栈可以解决一些很有价值的事情，比如：表达式求值。
下面我会通过LeetCode上《有效的括号》这个题进行引入，讲解表达式求值的实现，希望能为大家带来帮助。
一、有效的括号
点击跳转LeetCode：有效的括号
题目描述：
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
（一）题目分析
本题要求我们判断括号是否有效，那么我们需要知道什么形式的括号才是有效的？
1.括号的总数量一定是偶数个，并且左右括号各占一半；
2.左括号必须和与之对应的右括号相结合，既 ‘(’ 必须和 ‘)’ 对应，‘[’ 和 ‘]’ 以及 ‘{’ 和 ‘}’ 亦然；
3.必须先有左括号再有右括号。
通过上面的分析我们可以知道，遇到左括号就入栈，出现右括号就和栈区最后一个左括号进行匹配，匹配上了就出栈，否则就是无效的括号，并且最后栈区是空的。括号一定是成对出现的
int sz = strlen(s); if (sz % 2 != 0) return false;- 1
- 2
- 3
遇到左括号就入栈，遇到右括号就出栈
char* arr = (char*)malloc(sz); int a = 0; // 记录栈区字符的个数 for (int i = 0; i < sz; i++) { switch (s[i]) { case '(': case '[': case '{': arr[a++] = s[i]; break; case ')': if (a > 0 && arr[--a] == '(') break; else return false; case ']': if (a > 0 && arr[--a] == '[') break; else return false; case '}': if (a > 0 && arr[--a] == '{') break; else return false; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
最后我们还需要判断栈区是否为空，防止左括号比右括号多
if(a==0) return true; else return false;- 1
- 2
- 3
- 4
（二）整体代码
示例：
bool isValid(char* s) { int sz = strlen(s); if (sz % 2 != 0) return false; char* arr = (char*)malloc(sz); int a = 0; // 记录栈区字符的个数 for (int i = 0; i < sz; i++) { switch (s[i]) { case '(': case '[': case '{': arr[a++] = s[i]; break; case ')': if (a > 0 && arr[--a] == '(') break; else return false; case ']': if (a > 0 && arr[--a] == '[') break; else return false; case '}': if (a > 0 && arr[--a] == '{') break; else return false; } } if(a==0) return true; else return false; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
运行实例：
二、表达式求值
上一个例题我们写的十分简陋，虽然说是用到了栈，不过只是用到了它的思想而没有具体实现出来，下面一个例题熊猫我会直接先把栈区的操作实现出来，让大家真真正正滴了解一下栈的操作（防止大家觉得熊猫我不够专业）。
题目描述：
以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，
我们需要实现对算术四则混合运算表达式的求值。
测试数据：
3*(7-1)；1+2+3+4；88-15；(20+2)(6/2)；6+2*(3+6)。（一）题目分析
题目要求我们实现对算数四则混合运算表达式的求值，这里我们首先需要注意两点：
1.小括号的优先级最高，我们需要先进行括号里的表达式运算
2.乘法和除法的优先级高于加法和减法1.栈的基本操作：
#define MALLOC(ty,num) (ty*)malloc(sizeof(ty)*(num)) #define REALLOC(block,ty,num) (ty*)realloc(block,sizeof(ty)*(num)); #define OK 1 #define ERROR 0 #define INITNUM 5 //初始化顺序表长度 #define ADDNUM 3 //之后每次增加的长度 typedef double selemtype; typedef struct SQStack { selemtype* data; int length; int maxnum; }SQS; void Init(SQS* p) 栈的初始化 { assert(p); p->data = MALLOC(selemtype, INITNUM); if (!p->data) { return; } p->length = 0;//顺序栈下一个元素的下标 p->maxnum = INITNUM; } void Destroy(SQS* p) // 栈的销毁 { assert(p); free(p->data); p->length = 0; p->maxnum = 0; } static int Judge(SQS* p) // 判断栈区是否已满并扩容 { assert(p); if (p->length == p->maxnum)//满了 { selemtype* newblock = REALLOC(p->data, selemtype, p->length + ADDNUM); if (newblock == NULL) { return ERROR; } p->data = newblock; p->maxnum = p->length + ADDNUM; } return OK; } void Push(SQS* p, selemtype con) // 入栈 { assert(p); Judge(p); p->data[p->length] = con; p->length++; } void Pop(SQS* p) // 出栈 { assert(p); p->length--; } int JudgeOverflow(SQS* p) // 判断栈区是否为空 { assert(p); if (p->length == 0) { return ERROR; } else { return OK; } } selemtype GetTop(SQS* p) // 获取栈顶数据 { assert(p); return p->data[p->length - 1]; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
2. 大体思路：
由于小括号运算优先级最高，所以我们需要先计算括号内再计算括号外；
我们这里可以先判断小括号是否存在，如果没有遇到括号、或者遇到了左括号我们就继续进栈，直到遇到了右括号我们再出栈，
当然，出栈也有限制：
1.出到了左括号就停止出栈，这时一个括号内的表达式就计算结束了
2.如果栈空了就说明这整个表达式就计算结束了，此时我们就已经功德圆满啦（bushi）。selemtype Expression(char* str) { SQS s; Init(&s); double con = 0; // 表达式结果 char* p = NULL; // int i = 0; for (i = 0; str[i]; ) // 遍历字符串 { if (isdigit(str[i])) // 判断是数值 { // 本函数是将字符串转为double类型数据，并且返回转换数据结束时后一个位置的地址，我们将它存放在指针p中 //这里不可以直接 push(str[i]); //是为了防止参与运算的数值中有小数、以及不止一位数的数据 selemtype val = strtod(&str[i], &p); Push(&s, val); i = p - str; // 更新下标 } else // 符号 { if (str[i] != ')') { Push(&s, str[i]); } else // 如果遇到右括号我们就讲括号内的表达式进行一次求值 { con = Evaluation(&s); Push(&s, con); // 求得的值要继续入栈，最后需要再整体进行一次运算 } i++; // 更新下标 } } con = Evaluation(&s); // 整体结果运算 Destroy(&s); return con; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
经过上面的理想操作，我们就可以得到想要的结果，
为了便于下面运算函数的实现，我们大家可以通过下面的图解来大致了解操作过程。
3.具体计算过程：
这里我们不需要考虑括号，主要考虑的是优先级的问题（还有一些特殊情况）
下面我们先来画图分析一下：
selemtype Evaluation(SQS* ps) { selemtype con = 0; selemtype val1 = GetTop(ps); // 数值 Pop(ps); selemtype val2 = 0; while (JudgeOverflow(ps)) // 栈为空就退出 { switch ((char)GetTop(ps)) { case'+': { Pop(ps); // 将 '+' 出栈 val2 = GetTop(ps); Pop(ps); con += val1; val1 = val2; } break; case '-': { Pop(ps); if (!JudgeOverflow(ps)) // 特殊1.这个地方是要避免第一个数是负数 { con -= val1; return con; } val2 = GetTop(ps); Pop(ps); con -= val1; val1 = val2; } break; case '*': { Pop(ps); val1 *= GetTop(ps); Pop(ps); } break; case '/': { Pop(ps); val2 = GetTop(ps); Pop(ps); if (GetTop(ps) == '/') // 特殊2：出栈是后进先出的，因此如果出现连除情况需要特殊处理 val1 = val1 * val2; else val1 = val2 / val1; } break; case '(': Pop(ps); goto end; } } end: con += val1; return con; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
两种特殊情况：
（二）整体代码
示例：
#define _CRT_SECURE_NO_WARNINGS 1 #include#include #include #include #define MALLOC(ty,num) (ty*)malloc(sizeof(ty)*(num)) #define REALLOC(block,ty,num) (ty*)realloc(block,sizeof(ty)*(num)); #define OK 1 #define ERROR 0 #define INITNUM 5 //初始化顺序表长度 #define ADDNUM 3 //之后每次增加的长度 typedef double selemtype; typedef struct SQStack { selemtype* data; int length; int maxnum; }SQS; void Init(SQS* p) { assert(p); p->data = MALLOC(selemtype, INITNUM); if (!p->data) { return; } p->length = 0;//顺序栈下一个元素的下标 p->maxnum = INITNUM; } void Destroy(SQS* p) { assert(p); free(p->data); p->length = 0; p->maxnum = 0; } static int Judge(SQS* p) { assert(p); if (p->length == p->maxnum)//满了 { selemtype* newblock = REALLOC(p->data, selemtype, p->length + ADDNUM); if (newblock == NULL) { return ERROR; } p->data = newblock; p->maxnum = p->length + ADDNUM; } return OK; } //入栈 void Push(SQS* p, selemtype con) { assert(p); Judge(p); p->data[p->length] = con; p->length++; } void Pop(SQS* p) { assert(p); p->length--; } int JudgeOverflow(SQS* p) { assert(p); if (p->length == 0) { return ERROR; } else { return OK; } } selemtype GetTop(SQS* p) { assert(p); return p->data[p->length - 1]; } selemtype Evaluation(SQS* ps) { selemtype con = 0; selemtype val1 = GetTop(ps); // 数值 Pop(ps); selemtype val2 = 0; while (JudgeOverflow(ps)) { switch ((char)GetTop(ps)) { case'+': { Pop(ps); // 将 '+' 出栈 val2 = GetTop(ps); Pop(ps); con += val1; val1 = val2; } break; case '-': { Pop(ps); if (!JudgeOverflow(ps)) { con -= val1; return con; } val2 = GetTop(ps); Pop(ps); con -= val1; val1 = val2; } break; case '*': { Pop(ps); val1 *= GetTop(ps); Pop(ps); } break; case '/': { Pop(ps); val2 = GetTop(ps); Pop(ps); if (GetTop(ps) == '/') val1 = val1 * val2; else val1 = val2 / val1; } break; case '(': Pop(ps); goto end; } } end: con += val1; return con; } selemtype Expression(char* str) { SQS s; Init(&s); double con = 0; // 表达式结果 char* p = NULL; // int i = 0; for (i = 0; str[i]; ) // 遍历字符串 { if (isdigit(str[i])) // 数值 { selemtype val = strtod(&str[i], &p); Push(&s, val); i = p - str; // 更新下标 } else // 符号 { if (str[i] != ')') { Push(&s, str[i]); } else { con = Evaluation(&s); Push(&s, con); } i++; // 更新下标 } } con = Evaluation(&s); Destroy(&s); return con; } int main() { while (1) { printf("请输入表达式："); char str[100] = { 0 }; scanf("%s", str); selemtype con = 0;//表达式结果 con = Expression(str); printf("表达式结果为：%.2lf\n\n", con); } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
运行实例：
总结
以上就是表达式求值的全部内容，熊猫这边建议大家在学习的过程中可以尝试着做一些有趣的东西，这样不仅能够提高自己的学习积极性，对自己的实力也能做到很好的打磨，何乐而不为呢~。
那么今天就讲解到这里，如果有什么疑问或者建议都可以在评论区留言，感谢大家对
的支持。 -
相关阅读:
基于PHP的学生在线成绩管理系统
2023年软件测试之功能测试（完整版）
sip广播10W网络有源吸顶喇叭
5大组合拳，解决校园6大难题，护航教育信息化建设
2022牛客暑期多校训练营5（BCDFGHK）
盘点CSV文件在Excel中打开后乱码问题的三种处理方法
Docker网络功能
自用文章汇总
Seata 分布式事务框架
python查找与排序算法详解（示意图+代码、看完基础不成问题）
- 原文地址：https://blog.csdn.net/m0_66363962/article/details/127616275
