栈在表达式求值中的应用
表达式求值是程序设计语言中最基本的问题，在中缀表达式中不仅依赖运算符的优先级，而且还要处理括号。后缀表达式的运算符在操作数后面，在后缀表达式中已考虑了运算符的优先级，没有括号，只有操作数和运算符，更符合CPU的运算与处理。
中缀表达式转后缀表达式（手算）
中缀表达式A + B * (C - D) - E / F化为后缀表达式采用左优先的原则（没有运算符更高级的一律从左往右进行匹配，保证算法的唯一性）。
在这表达式中先进行( )中进行运算，并将运算符放在操作数后面，得CD-。
此时CD-为一个整体并根据运算符优先级与B*进行运算得BCD-*。
再与A+进行运算，得ABCD-*+，剩下就是- E / F部分，先进行除运算得EF/，再ABCD-*+与EF/进行减运算，得最终结果ABCD-*+EF/-。
中缀表达式转后缀表达式（机算）
初始化一个栈，用于保存展示还不能确定运算顺序的运算符。
从左到右处理各个元素，直到末尾。可能遇到三种情况。
- 遇到操作数。直接加入后缀表达式。
- 遇到界限符。遇到
"("直接入栈：遇到")"则依次弹出栈内运算符并加入后缀表达式，直到弹出"("为止。但"("不加入到后缀表达式中。 - 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到
"("或栈空则停止。之后再把当前运算符入栈。
具体代码实现
// 判断是否是操作数
int isNumber(char e)
{
if (e == '+' || e == '-' || e == '*' || e == '/' || e == '(' || e == ')')
{
return false;
}
else
{
return true;
}
}
// 中缀表达式转后缀表达式
Elemtype *InfixToSuffix(Elemtype expression[], int length)
{
SqStack S;
// 初始化栈
InitStack(&S);
// 存储后缀表达式 在堆中开辟空间用于返回 用calloc初始全为0，以防去除'()'后多余数据会造成结果错误
char *SuffixExpression = (char *)calloc(sizeof(char) * length,sizeof(char));
// 记录储存后缀表达式的指针
int j = 0;
// 存储栈顶元素
char topEl;
// 存储出栈元素
char popEl;
for (size_t i = 0; i < length; i++)
{
if (isNumber(expression[i]))
{
// 是数字就直接加入到后缀表达式中
SuffixExpression[j] = expression[i];
j++;
}
// 不是数字则为操作符
else
{
// 如果栈为空或为'('，则直接加入到栈中
if (StackEmpty(&S) || expression[i] == '(')
{
Push(&S, expression[i]);
}
// 此时栈非空，并且扫描到的为 + 或 - 则栈中的优先级必定是高于或等于当前运算符
else if (expression[i] == '+' || expression[i] == '-')
{
// 获取栈顶元素
GetTop(&S, &topEl);
if (topEl != '(')
{
// 将栈弹空或者遇到'('则停止
while (!StackEmpty(&S) && topEl != '(')
{
Pop(&S, &popEl);
// 弹出的元素不为'('，则加入到后缀表达式中
if (popEl != '(')
{
SuffixExpression[j] = popEl;
j++;
}
}
// 弹出所有元素后将自身入栈
Push(&S, expression[i]);
}
// 此时栈顶为'('则直接入栈
else
{
Push(&S, expression[i]);
}
}
// 此时为 * 或 / ，可能栈中优先级较低，所以要进行判断
else if (expression[i] == '*' || expression[i] == '/')
{
// 获取栈顶元素
GetTop(&S, &topEl);
// 若栈顶为 + 或 - 说明优先级低于扫描到的，不能进行出栈操作，而是将扫描到的表达式入栈
if (topEl == '+' || topEl == '-' || topEl == '(')
{
Push(&S, expression[i]);
}
// 直接出栈
else
{
Pop(&S, &popEl);
while (!StackEmpty(&S) && popEl != '(')
{
SuffixExpression[j] = popEl;
j++;
}
}
}
// 当扫描到')'则将'('后的包括'('在内的所有操作符都弹出
else if (expression[i] == ')')
{
// 弹出元素
Pop(&S, &popEl);
while (popEl != '(')
{
// 将非'('的操作符加入到后缀表达式中
if (popEl != '(')
{
SuffixExpression[j] = popEl;
j++;
}
Pop(&S, &popEl);
}
}
}
}
// 将栈中剩下的操作符弹出
while (!StackEmpty(&S))
{
Pop(&S, &popEl);
SuffixExpression[j] = popEl;
j++;
}
return SuffixExpression;
}后缀表达式计算（手算）
方法：
从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数。
例：A + B * (C - D) - E / F转为后缀为ABCD-*+EF/-，计算先扫描到第一个操作符，然后将操作符左边两个操作数进行运算，则CD-进行运算得C-D，后将C-D视为一个整体，然后继续扫描下一个操作数*，然后将C-D与左边的B进行运算得B*(C-D)再视为一个整体，再扫描下一个操作数+，同样的将A与B*(C-D)进行运算得A + B*(C-D)，以此类推就可以将后缀表达式还原成中缀表达式并计算出值。
后缀表达式计算（机算）
用栈实现后缀表达式的计算：
- 用左往右扫描下一个元素，直到处理完所有元素
- 若扫描到操作数则直接压入栈，并回到(1)；否则执行(3)
- 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到(1)的步骤。
