后缀表达式，由波兰科学家在20世纪50年代提出，将运算符放在数字后面，更便于计算机去计算，而我们平常看到的 1 2、5 * 10 等，都是中缀表达式，这种方式，符合人类的思考方式。举几个例子：
代码语言：javascript复制5 4 => 5 4
1 2 * 3 => 1 2 3 *
8 ( 3 – 1 ) * 5 => 8 3 1 – 5 * 左侧为中缀表达式，右侧为后缀表达式。那这种转换的规则和方法是什么呢？首先我们来看一下规则： 【后缀表达式转换规则】
对于数字：直接输出 对于符号： 左括号：进栈 运算符号：与栈顶符号进行优先级比较 若栈顶符号优先级低：此符号进栈 （默认栈顶若是左括号，左括号优先级最低） 若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈 右括号：将栈顶符号弹出并输出，直到匹配左括号
【使用栈模型实现以上功能】 注意，以下代码需要用到栈模型链式储存的实现头文件 LinkStack.h 和 LinkStack.c：
代码语言：javascript复制#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 != ‘ ’)
{
printf(“%c”, c);
}
}
void process(char* code)
{
LinkStack* stack = LinkStack_Create();
int i = 0;
while (code[i] != ‘ ’)
{
// 如果是数字直接输出
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;
}
