一、什么是中缀和后缀表达式1.1 三种表达式类型示例说明中缀3 4 * 2运算符在两个操作数之间人类习惯前缀 3 * 4 2运算符在前面后缀3 4 2 * 运算符在后面计算机容易处理1.2 为什么用后缀表达式计算34*2时人类知道先乘后加。但计算机从左到右扫描遇到时不知道后面还有*。后缀表达式3 4 2 * 就没有这个问题遇到数字就压栈遇到运算符就弹出两个数计算结果压栈不需要知道优先级顺序扫描即可二、计算后缀表达式先学会计算后缀再学转换。因为转换过程中也要用到这个逻辑。2.1 算法思路用栈存储数字从左到右扫描后缀表达式遇到数字压入栈遇到运算符弹出栈顶两个数字先弹出右操作数再弹出左操作数计算后结果压栈扫描结束栈顶就是最终结果示例3 4 2 * text扫描3 → 栈: [3] 扫描4 → 栈: [3, 4] 扫描2 → 栈: [3, 4, 2] 扫描* → 弹出2和4计算4*28压栈 → 栈: [3, 8] 扫描 → 弹出8和3计算3811压栈 → 栈: [11] 结果: 112.2 代码实现c#include stdio.h #include stdlib.h #include ctype.h #include string.h #define MAX_SIZE 100 // 数字栈 typedef struct { double data[MAX_SIZE]; int top; } NumStack; void initNumStack(NumStack *s) { s-top -1; } int isNumStackEmpty(NumStack *s) { return s-top -1; } int isNumStackFull(NumStack *s) { return s-top MAX_SIZE - 1; } void pushNum(NumStack *s, double val) { if (isNumStackFull(s)) { printf(栈满\n); return; } s-data[s-top] val; } double popNum(NumStack *s) { if (isNumStackEmpty(s)) { printf(栈空\n); return 0; } return s-data[s-top--]; } // 计算后缀表达式 double evalPostfix(const char *expr) { NumStack stack; initNumStack(stack); char *token strtok((char*)expr, ); while (token ! NULL) { // 如果是数字 if (isdigit(token[0]) || (token[0] - isdigit(token[1]))) { pushNum(stack, atof(token)); } // 如果是运算符 else { double right popNum(stack); double left popNum(stack); double result; switch (token[0]) { case : result left right; break; case -: result left - right; break; case *: result left * right; break; case /: if (right 0) { printf(除数不能为0\n); return 0; } result left / right; break; default: printf(未知运算符: %s\n, token); return 0; } pushNum(stack, result); } token strtok(NULL, ); } return popNum(stack); } int main() { char expr[] 3 4 2 * ; printf(%s %.2f\n, expr, evalPostfix(expr)); char expr2[] 10 5 / 2 3 * ; printf(%s %.2f\n, expr2, evalPostfix(expr2)); return 0; }运行结果text3 4 2 * 11.00 10 5 / 2 3 * 8.00三、中缀转后缀3.1 运算符优先级运算符优先级()最高*/2-13.2 转换算法用栈存储运算符从左到右扫描中缀表达式遇到数字直接输出遇到左括号(入栈遇到右括号)不断弹出栈顶运算符并输出直到遇到左括号左括号弹出但不输出遇到运算符栈空或栈顶是左括号直接入栈否则如果当前运算符优先级 栈顶运算符优先级入栈否则优先级 栈顶弹出栈顶并输出继续比较新栈顶扫描结束后弹出栈中所有运算符并输出示例3 4 * 2text扫描3 → 输出: 3 扫描 → 栈空入栈 → 栈: [] 扫描4 → 输出: 3 4 扫描* → *优先级 入栈 → 栈: [ *] 扫描2 → 输出: 3 4 2 结束 → 弹出栈: 输出 * 最终: 3 4 2 * 示例(1 2) * 3text扫描( → 入栈 → 栈: [(] 扫描1 → 输出: 1 扫描 → 栈顶是(入栈 → 栈: [( ] 扫描2 → 输出: 1 2 扫描) → 弹出并输出 → 输出: 1 2 弹出(丢弃 扫描* → 栈空入栈 → 栈: [*] 扫描3 → 输出: 1 2 3 结束 → 弹出* → 输出: 1 2 3 *3.3 代码实现c#include stdio.h #include stdlib.h #include ctype.h #include string.h #define MAX_SIZE 100 // 运算符栈 typedef struct { char data[MAX_SIZE]; int top; } CharStack; void initCharStack(CharStack *s) { s-top -1; } int isCharStackEmpty(CharStack *s) { return s-top -1; } int isCharStackFull(CharStack *s) { return s-top MAX_SIZE - 1; } void pushChar(CharStack *s, char val) { if (isCharStackFull(s)) return; s-data[s-top] val; } char popChar(CharStack *s) { if (isCharStackEmpty(s)) return \0; return s-data[s-top--]; } char peekChar(CharStack *s) { if (isCharStackEmpty(s)) return \0; return s-data[s-top]; } // 获取优先级 int priority(char op) { if (op || op -) return 1; if (op * || op /) return 2; return 0; } // 判断是否为运算符 int isOperator(char c) { return c || c - || c * || c /; } // 中缀转后缀 void infixToPostfix(const char *infix, char *postfix) { CharStack stack; initCharStack(stack); int pos 0; for (int i 0; infix[i] ! \0; i) { char ch infix[i]; // 跳过空格 if (ch ) continue; // 数字直接输出 if (isdigit(ch)) { while (isdigit(infix[i]) || infix[i] .) { postfix[pos] infix[i]; } postfix[pos] ; // 分隔符 i--; // 回退一个字符 } // 左括号入栈 else if (ch () { pushChar(stack, ch); } // 右括号弹出直到左括号 else if (ch )) { while (!isCharStackEmpty(stack) peekChar(stack) ! () { postfix[pos] popChar(stack); postfix[pos] ; } popChar(stack); // 弹出左括号 } // 运算符 else if (isOperator(ch)) { while (!isCharStackEmpty(stack) peekChar(stack) ! ( priority(peekChar(stack)) priority(ch)) { postfix[pos] popChar(stack); postfix[pos] ; } pushChar(stack, ch); } } // 弹出栈中剩余运算符 while (!isCharStackEmpty(stack)) { postfix[pos] popChar(stack); postfix[pos] ; } postfix[pos - 1] \0; // 去掉最后多余的空格 } int main() { char infix1[] 34*2; char infix2[] (12)*3; char infix3[] 10/(3-1); char postfix[MAX_SIZE]; infixToPostfix(infix1, postfix); printf(中缀: %s\n后缀: %s\n, infix1, postfix); infixToPostfix(infix2, postfix); printf(中缀: %s\n后缀: %s\n, infix2, postfix); infixToPostfix(infix3, postfix); printf(中缀: %s\n后缀: %s\n, infix3, postfix); return 0; }运行结果text中缀: 34*2 后缀: 3 4 2 * 中缀: (12)*3 后缀: 1 2 3 * 中缀: 10/(3-1) 后缀: 10 3 1 - /四、完整计算器实现把中缀转后缀和后缀计算结合起来实现一个完整计算器。c#include stdio.h #include stdlib.h #include ctype.h #include string.h #define MAX_SIZE 100 // 运算符栈 typedef struct { char data[MAX_SIZE]; int top; } OpStack; void initOpStack(OpStack *s) { s-top -1; } int isOpEmpty(OpStack *s) { return s-top -1; } int isOpFull(OpStack *s) { return s-top MAX_SIZE - 1; } void pushOp(OpStack *s, char val) { if (!isOpFull(s)) s-data[s-top] val; } char popOp(OpStack *s) { return isOpEmpty(s) ? \0 : s-data[s-top--]; } char peekOp(OpStack *s) { return isOpEmpty(s) ? \0 : s-data[s-top]; } // 数字栈 typedef struct { double data[MAX_SIZE]; int top; } NumStack; void initNumStack(NumStack *s) { s-top -1; } int isNumEmpty(NumStack *s) { return s-top -1; } int isNumFull(NumStack *s) { return s-top MAX_SIZE - 1; } void pushNum(NumStack *s, double val) { if (!isNumFull(s)) s-data[s-top] val; } double popNum(NumStack *s) { return isNumEmpty(s) ? 0 : s-data[s-top--]; } int priority(char op) { if (op || op -) return 1; if (op * || op /) return 2; return 0; } int isOperator(char c) { return c || c - || c * || c /; } // 计算后缀表达式 double evalPostfix(const char *postfix) { NumStack stack; initNumStack(stack); for (int i 0; postfix[i] ! \0; i) { if (isdigit(postfix[i])) { double num 0; while (isdigit(postfix[i])) { num num * 10 (postfix[i] - 0); i; } pushNum(stack, num); } else if (isOperator(postfix[i])) { double right popNum(stack); double left popNum(stack); double result; switch (postfix[i]) { case : result left right; break; case -: result left - right; break; case *: result left * right; break; case /: result left / right; break; default: return 0; } pushNum(stack, result); } } return popNum(stack); } // 中缀转后缀并计算 double calculate(const char *infix) { OpStack stack; initOpStack(stack); char postfix[MAX_SIZE]; int pos 0; for (int i 0; infix[i] ! \0; i) { char ch infix[i]; if (ch ) continue; if (isdigit(ch)) { while (isdigit(infix[i]) || infix[i] .) { postfix[pos] infix[i]; } postfix[pos] ; i--; } else if (ch () { pushOp(stack, ch); } else if (ch )) { while (!isOpEmpty(stack) peekOp(stack) ! () { postfix[pos] popOp(stack); postfix[pos] ; } popOp(stack); } else if (isOperator(ch)) { while (!isOpEmpty(stack) peekOp(stack) ! ( priority(peekOp(stack)) priority(ch)) { postfix[pos] popOp(stack); postfix[pos] ; } pushOp(stack, ch); } } while (!isOpEmpty(stack)) { postfix[pos] popOp(stack); postfix[pos] ; } postfix[pos - 1] \0; printf(后缀表达式: %s\n, postfix); return evalPostfix(postfix); } int main() { char expr[MAX_SIZE]; printf(请输入表达式支持 - * / 和括号: ); fgets(expr, MAX_SIZE, stdin); expr[strcspn(expr, \n)] \0; double result calculate(expr); printf(结果: %.2f\n, result); return 0; }运行效果text请输入表达式支持 - * / 和括号: (12)*(34) 后缀表达式: 1 2 3 4 * 结果: 21.00五、复杂度分析操作时间复杂度空间复杂度中缀转后缀O(n)O(n)后缀计算O(n)O(n)整体O(n)O(n)六、小结这一篇我们用栈实现了完整的四则运算计算器内容要点后缀表达式没有括号和优先级计算机容易处理中缀转后缀用运算符栈根据优先级决定是否弹出后缀计算用数字栈遇到运算符就弹出两个数计算完整计算器两步合一支持 - * / 和括号核心规则数字直接输出左括号入栈右括号弹出直到左括号运算符优先级高于栈顶才入栈否则弹出下一篇我们讲队列。七、思考题后缀表达式5 1 2 4 * 3 -的值是多少手动计算一下。中缀转后缀算法中为什么要用而不是来比较优先级如何让计算器支持负数和浮点数尝试实现一个支持乘方^运算右结合的表达式求值器。欢迎在评论区讨论你的答案。
【数据结构与算法】第13篇：栈（三）：中缀表达式转后缀表达式及计算
一、什么是中缀和后缀表达式1.1 三种表达式类型示例说明中缀3 4 * 2运算符在两个操作数之间人类习惯前缀 3 * 4 2运算符在前面后缀3 4 2 * 运算符在后面计算机容易处理1.2 为什么用后缀表达式计算34*2时人类知道先乘后加。但计算机从左到右扫描遇到时不知道后面还有*。后缀表达式3 4 2 * 就没有这个问题遇到数字就压栈遇到运算符就弹出两个数计算结果压栈不需要知道优先级顺序扫描即可二、计算后缀表达式先学会计算后缀再学转换。因为转换过程中也要用到这个逻辑。2.1 算法思路用栈存储数字从左到右扫描后缀表达式遇到数字压入栈遇到运算符弹出栈顶两个数字先弹出右操作数再弹出左操作数计算后结果压栈扫描结束栈顶就是最终结果示例3 4 2 * text扫描3 → 栈: [3] 扫描4 → 栈: [3, 4] 扫描2 → 栈: [3, 4, 2] 扫描* → 弹出2和4计算4*28压栈 → 栈: [3, 8] 扫描 → 弹出8和3计算3811压栈 → 栈: [11] 结果: 112.2 代码实现c#include stdio.h #include stdlib.h #include ctype.h #include string.h #define MAX_SIZE 100 // 数字栈 typedef struct { double data[MAX_SIZE]; int top; } NumStack; void initNumStack(NumStack *s) { s-top -1; } int isNumStackEmpty(NumStack *s) { return s-top -1; } int isNumStackFull(NumStack *s) { return s-top MAX_SIZE - 1; } void pushNum(NumStack *s, double val) { if (isNumStackFull(s)) { printf(栈满\n); return; } s-data[s-top] val; } double popNum(NumStack *s) { if (isNumStackEmpty(s)) { printf(栈空\n); return 0; } return s-data[s-top--]; } // 计算后缀表达式 double evalPostfix(const char *expr) { NumStack stack; initNumStack(stack); char *token strtok((char*)expr, ); while (token ! NULL) { // 如果是数字 if (isdigit(token[0]) || (token[0] - isdigit(token[1]))) { pushNum(stack, atof(token)); } // 如果是运算符 else { double right popNum(stack); double left popNum(stack); double result; switch (token[0]) { case : result left right; break; case -: result left - right; break; case *: result left * right; break; case /: if (right 0) { printf(除数不能为0\n); return 0; } result left / right; break; default: printf(未知运算符: %s\n, token); return 0; } pushNum(stack, result); } token strtok(NULL, ); } return popNum(stack); } int main() { char expr[] 3 4 2 * ; printf(%s %.2f\n, expr, evalPostfix(expr)); char expr2[] 10 5 / 2 3 * ; printf(%s %.2f\n, expr2, evalPostfix(expr2)); return 0; }运行结果text3 4 2 * 11.00 10 5 / 2 3 * 8.00三、中缀转后缀3.1 运算符优先级运算符优先级()最高*/2-13.2 转换算法用栈存储运算符从左到右扫描中缀表达式遇到数字直接输出遇到左括号(入栈遇到右括号)不断弹出栈顶运算符并输出直到遇到左括号左括号弹出但不输出遇到运算符栈空或栈顶是左括号直接入栈否则如果当前运算符优先级 栈顶运算符优先级入栈否则优先级 栈顶弹出栈顶并输出继续比较新栈顶扫描结束后弹出栈中所有运算符并输出示例3 4 * 2text扫描3 → 输出: 3 扫描 → 栈空入栈 → 栈: [] 扫描4 → 输出: 3 4 扫描* → *优先级 入栈 → 栈: [ *] 扫描2 → 输出: 3 4 2 结束 → 弹出栈: 输出 * 最终: 3 4 2 * 示例(1 2) * 3text扫描( → 入栈 → 栈: [(] 扫描1 → 输出: 1 扫描 → 栈顶是(入栈 → 栈: [( ] 扫描2 → 输出: 1 2 扫描) → 弹出并输出 → 输出: 1 2 弹出(丢弃 扫描* → 栈空入栈 → 栈: [*] 扫描3 → 输出: 1 2 3 结束 → 弹出* → 输出: 1 2 3 *3.3 代码实现c#include stdio.h #include stdlib.h #include ctype.h #include string.h #define MAX_SIZE 100 // 运算符栈 typedef struct { char data[MAX_SIZE]; int top; } CharStack; void initCharStack(CharStack *s) { s-top -1; } int isCharStackEmpty(CharStack *s) { return s-top -1; } int isCharStackFull(CharStack *s) { return s-top MAX_SIZE - 1; } void pushChar(CharStack *s, char val) { if (isCharStackFull(s)) return; s-data[s-top] val; } char popChar(CharStack *s) { if (isCharStackEmpty(s)) return \0; return s-data[s-top--]; } char peekChar(CharStack *s) { if (isCharStackEmpty(s)) return \0; return s-data[s-top]; } // 获取优先级 int priority(char op) { if (op || op -) return 1; if (op * || op /) return 2; return 0; } // 判断是否为运算符 int isOperator(char c) { return c || c - || c * || c /; } // 中缀转后缀 void infixToPostfix(const char *infix, char *postfix) { CharStack stack; initCharStack(stack); int pos 0; for (int i 0; infix[i] ! \0; i) { char ch infix[i]; // 跳过空格 if (ch ) continue; // 数字直接输出 if (isdigit(ch)) { while (isdigit(infix[i]) || infix[i] .) { postfix[pos] infix[i]; } postfix[pos] ; // 分隔符 i--; // 回退一个字符 } // 左括号入栈 else if (ch () { pushChar(stack, ch); } // 右括号弹出直到左括号 else if (ch )) { while (!isCharStackEmpty(stack) peekChar(stack) ! () { postfix[pos] popChar(stack); postfix[pos] ; } popChar(stack); // 弹出左括号 } // 运算符 else if (isOperator(ch)) { while (!isCharStackEmpty(stack) peekChar(stack) ! ( priority(peekChar(stack)) priority(ch)) { postfix[pos] popChar(stack); postfix[pos] ; } pushChar(stack, ch); } } // 弹出栈中剩余运算符 while (!isCharStackEmpty(stack)) { postfix[pos] popChar(stack); postfix[pos] ; } postfix[pos - 1] \0; // 去掉最后多余的空格 } int main() { char infix1[] 34*2; char infix2[] (12)*3; char infix3[] 10/(3-1); char postfix[MAX_SIZE]; infixToPostfix(infix1, postfix); printf(中缀: %s\n后缀: %s\n, infix1, postfix); infixToPostfix(infix2, postfix); printf(中缀: %s\n后缀: %s\n, infix2, postfix); infixToPostfix(infix3, postfix); printf(中缀: %s\n后缀: %s\n, infix3, postfix); return 0; }运行结果text中缀: 34*2 后缀: 3 4 2 * 中缀: (12)*3 后缀: 1 2 3 * 中缀: 10/(3-1) 后缀: 10 3 1 - /四、完整计算器实现把中缀转后缀和后缀计算结合起来实现一个完整计算器。c#include stdio.h #include stdlib.h #include ctype.h #include string.h #define MAX_SIZE 100 // 运算符栈 typedef struct { char data[MAX_SIZE]; int top; } OpStack; void initOpStack(OpStack *s) { s-top -1; } int isOpEmpty(OpStack *s) { return s-top -1; } int isOpFull(OpStack *s) { return s-top MAX_SIZE - 1; } void pushOp(OpStack *s, char val) { if (!isOpFull(s)) s-data[s-top] val; } char popOp(OpStack *s) { return isOpEmpty(s) ? \0 : s-data[s-top--]; } char peekOp(OpStack *s) { return isOpEmpty(s) ? \0 : s-data[s-top]; } // 数字栈 typedef struct { double data[MAX_SIZE]; int top; } NumStack; void initNumStack(NumStack *s) { s-top -1; } int isNumEmpty(NumStack *s) { return s-top -1; } int isNumFull(NumStack *s) { return s-top MAX_SIZE - 1; } void pushNum(NumStack *s, double val) { if (!isNumFull(s)) s-data[s-top] val; } double popNum(NumStack *s) { return isNumEmpty(s) ? 0 : s-data[s-top--]; } int priority(char op) { if (op || op -) return 1; if (op * || op /) return 2; return 0; } int isOperator(char c) { return c || c - || c * || c /; } // 计算后缀表达式 double evalPostfix(const char *postfix) { NumStack stack; initNumStack(stack); for (int i 0; postfix[i] ! \0; i) { if (isdigit(postfix[i])) { double num 0; while (isdigit(postfix[i])) { num num * 10 (postfix[i] - 0); i; } pushNum(stack, num); } else if (isOperator(postfix[i])) { double right popNum(stack); double left popNum(stack); double result; switch (postfix[i]) { case : result left right; break; case -: result left - right; break; case *: result left * right; break; case /: result left / right; break; default: return 0; } pushNum(stack, result); } } return popNum(stack); } // 中缀转后缀并计算 double calculate(const char *infix) { OpStack stack; initOpStack(stack); char postfix[MAX_SIZE]; int pos 0; for (int i 0; infix[i] ! \0; i) { char ch infix[i]; if (ch ) continue; if (isdigit(ch)) { while (isdigit(infix[i]) || infix[i] .) { postfix[pos] infix[i]; } postfix[pos] ; i--; } else if (ch () { pushOp(stack, ch); } else if (ch )) { while (!isOpEmpty(stack) peekOp(stack) ! () { postfix[pos] popOp(stack); postfix[pos] ; } popOp(stack); } else if (isOperator(ch)) { while (!isOpEmpty(stack) peekOp(stack) ! ( priority(peekOp(stack)) priority(ch)) { postfix[pos] popOp(stack); postfix[pos] ; } pushOp(stack, ch); } } while (!isOpEmpty(stack)) { postfix[pos] popOp(stack); postfix[pos] ; } postfix[pos - 1] \0; printf(后缀表达式: %s\n, postfix); return evalPostfix(postfix); } int main() { char expr[MAX_SIZE]; printf(请输入表达式支持 - * / 和括号: ); fgets(expr, MAX_SIZE, stdin); expr[strcspn(expr, \n)] \0; double result calculate(expr); printf(结果: %.2f\n, result); return 0; }运行效果text请输入表达式支持 - * / 和括号: (12)*(34) 后缀表达式: 1 2 3 4 * 结果: 21.00五、复杂度分析操作时间复杂度空间复杂度中缀转后缀O(n)O(n)后缀计算O(n)O(n)整体O(n)O(n)六、小结这一篇我们用栈实现了完整的四则运算计算器内容要点后缀表达式没有括号和优先级计算机容易处理中缀转后缀用运算符栈根据优先级决定是否弹出后缀计算用数字栈遇到运算符就弹出两个数计算完整计算器两步合一支持 - * / 和括号核心规则数字直接输出左括号入栈右括号弹出直到左括号运算符优先级高于栈顶才入栈否则弹出下一篇我们讲队列。七、思考题后缀表达式5 1 2 4 * 3 -的值是多少手动计算一下。中缀转后缀算法中为什么要用而不是来比较优先级如何让计算器支持负数和浮点数尝试实现一个支持乘方^运算右结合的表达式求值器。欢迎在评论区讨论你的答案。
