后缀表达式，由波兰科学家在20世纪50年代提出，将运算符放在数字后面，更便于计算机去计算，而我们平常看到的 1 + 2、5 * 10 等，都是中缀表达式，这种方式，符合人类的思考方式。举几个例子：

  1. 5 + 4 => 5 4 +
  2. 1 + 2 * 3 => 1 2 3 * +
  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;
}