后缀表达式,由波兰科学家在20世纪50年代提出,将运算符放在数字后面,更便于计算机去计算,而我们平常看到的 1 + 2、5 * 10 等,都是中缀表达式,这种方式,符合人类的思考方式。举几个例子:
- 5 + 4 => 5 4 +
- 1 + 2 * 3 => 1 2 3 * +
- 8 + ( 3 – 1 ) * 5 => 8 3 1 – 5 * +
左侧为中缀表达式,右侧为后缀表达式。那这种转换的规则和方法是什么呢?首先我们来看一下规则:
【后缀表达式转换规则】
对于数字:直接输出 对于符号: 左括号:进栈 运算符号:与栈顶符号进行优先级比较 若栈顶符号优先级低:此符号进栈 (默认栈顶若是左括号,左括号优先级最低) 若栈顶符号优先级不低:将栈顶符号弹出并输出,之后进栈 右括号:将栈顶符号弹出并输出,直到匹配左括号
【使用栈模型实现以上功能】
注意,以下代码需要用到栈模型链式储存的实现头文件 LinkStack.h 和 LinkStack.c:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "LinkStack.h" // 判断是不是数字 int is_num(char ch) { return ch >= '0' && ch <= '9'; } // 判断是不是左括号 int is_left(char ch) { return ch == '('; } // 判断是不是右括号 int is_right(char ch) { return ch == ')'; } // 判断是不是操作符 int is_operator(char ch) { return ch == '+' || ch == '-' || ch == '*' || ch == '/'; } // 判断优先级 int priority(char ch) { int result = 0; if (ch == '+' || ch == '-') result = 1; else if (ch == '*' || ch == '/') result = 2; return result; } void output(char c) { //字符不为0便输出 if (c != '\0') { printf("%c", c); } } void process(char* code) { LinkStack* stack = LinkStack_Create(); int i = 0; while (code[i] != '\0') { // 如果是数字直接输出 if (is_num(code[i])) { output(code[i]); } // 判断是不是操作符 if (is_operator(code[i])) { // 若栈顶符号优先级低:此符号进栈 //(默认栈顶若是左括号,左括号优先级最低) // 若栈顶符号优先级不低:将栈顶符号弹出并输出 while (priority(code[i]) <= priority((char)(int)LinkStack_Top(stack))) { // 弹出并输出 output((char)(int)LinkStack_Pop(stack)); } // 之后压栈 LinkStack_Push(stack, (void*)(int)code[i]); } // 判断是不是左括号 if (is_left(code[i])) { LinkStack_Push(stack, (void*)(int)code[i]); } // 判断是不是右括号,如果是与栈内左括号匹配 if (is_right(code[i])) { // 循环判断是不是左括号,不是则弹出栈顶元素,循环弹出直至遇到左括号为止 while (!is_left((char)(int)LinkStack_Top(stack))) { // 弹出并输出栈顶内容 output((char)(int)LinkStack_Pop(stack)); } // 此时弹出的一定是左括号 LinkStack_Pop(stack); } // 下标++ i++; } while (LinkStack_Size(stack)) { // 输出栈中内容 output((char)(int)LinkStack_Pop(stack)); } // 销毁栈 LinkStack_Destroy(stack); } int main(int argc, char* argv[]) { char* code = "8+(3-1)*5"; process(code); return 0; }