中缀表达式
运算符号在数字中间
后缀表达式
运算符号在数字之后
计算机计算计算的是后缀表达式
中缀变后缀举例
5 + 3 -> 5 3 +
1 + 2 * 3 -> 1 2 3 * +
9 + (3 - 1) * 5 -> 9 3 1 - 5 * +
中缀变后缀算法
···遍历中缀表达式中的数字和符号
·········对于数字：直接输出
·········对于符号：
······················左括号：进栈
······················符号 ：与栈顶符号进行优先级比较
································栈顶符号优先级低，进栈
································栈顶符号优先级不低，将栈顶符号弹出并输出之后在进栈
······················右括号：找到栈顶符号弹出并输出，直到找到匹配的左括号
···遍历结束，将栈中所有符号弹出并输出
伪代码
void transform (需要遍历的数组)
{
创建栈；
int i;
while (判断是否循环到最后了)
if (如果是数字)
{
直接输出
}
if (如果是左符号)
{
进栈
}
if (如果是符号)
{
if (priority(当前数字优先级) 《= priority(栈顶元素优先级))
栈顶弹出；
进栈（无论优先级高低都需要进栈）；
}
if (右括号)
{
while (栈顶是不是左括号)
出栈；
}
else
报错
}
代码
#include
#include "LinkStack.h"
int isNumber(char c)
{
return ('0' <= c) && (c <= '9');
}
int isOperator(char c)
{
return (c == '+') || (c == '-') || (c == '*') || (c == '/');
}
int isLeft(char c)
{
return (c == '(');
}
int isRight(char c)
{
return (c == ')');
}
int priority(char c)
{
int ret = 0;
if( (c == '+') || (c == '-') )
{
ret = 1;
}
if( (c == '*') || (c == '/') )
{
ret = 2;
}
return ret;
}
void output(char c)
{
if( c != ' ' )
{
printf("%c", c);
}
}
void transform(const char* exp)
{
LinkStack* stack = LinkStack_Create();
int i = 0;
while( exp[i] != ' ' )
{
if( isNumber(exp[i]) )
{
output(exp[i]);
}
else if( isOperator(exp[i]) )
{
while( priority(exp[i]) <= priority((char)(int)LinkStack_Top(stack)) )
{
output((char)(int)LinkStack_Pop(stack));
}
LinkStack_Push(stack, (void*)(int)exp[i]);
}
else if( isLeft(exp[i]) )
{
LinkStack_Push(stack, (void*)(int)exp[i]);
}
else if( isRight(exp[i]) )
{
char c = ' ';
while( !isLeft((char)(int)LinkStack_Top(stack)) )
{
output((char)(int)LinkStack_Pop(stack));
}
LinkStack_Pop(stack);
}
else
{
printf("Invalid expression!");
break;
}
i++;
}
while( (LinkStack_Size(stack) > 0) && (exp[i] == ' ') )
{
output((char)(int)LinkStack_Pop(stack));
}
LinkStack_Destroy(stack);
}
int main()
{
transform("9+(3-1)*5+8/2");
printf("n");
return 0;
}