堆栈应用
括号匹配问题: 假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个函数，用来判别表达式中括号是否正确配对，并设计一个测试主函数。
算法思想: 检验括号是否配对可以设置一个栈，每读入一个括号，如果是左括号，则直接进栈，如果读入的是右括号，并且与当前栈顶的左括号是同类型的，则说明括号是配对的，将栈顶的左括号出栈，否则不配对。如果输入序列已经读完，而栈中仍然有等待配对的左括号，则该括号不配对。
代码实现
<pre class="cm-s-default" style="color:rgb( 89 , 89 , 89 );margin:0px;padding:0px;background-image:none;background-attachment:scroll;background-color:rgba( 0 , 0 , 0 , 0 );background-position:0% 0%;background-repeat:repeat repeat">#include
include
include
include "string.h"
/宏定义和链栈类型定义/
typedef char DataType;
include "LinkStack.h" //包括链栈实现文件
int Match(DataType e,DataType ch); //检验括号是否配对函数
int main()
{
LinkStack S;
char *p;
DataType e;
DataType ch[60];
InitStack(&S); //初始化链栈
printf("请输入带括号的表达式");
gets(ch);
p=ch;
while(*p)
{
switch(*p)
{
case '(':
case '[':
case '{':
PushStack(S,*p++);
break;
case ')':
case ']':
case '}':
if (StackEmpty(S))
{
printf("缺少左括号。\n");
return 0;
}
else
{
GetTop(S,&e);
if (Match(e,*p))
{
PopStack(S,&e);
}
else
{
printf("左括号不配对\n");
return 0;
}
}
default: //如果是其他字符，则不处理，直接指向下一个字符
p++;
}
}
if (StackEmpty(S))
{
printf("括号匹配\n");
return 1;
}
else
{
printf("缺少右括号\n");
return 0;
}}
int Match(DataType e,DataType ch)
{
if (e=='('&&ch==')')
{
return 1;
}
else if (e=='['&&ch==']')
{
return 1;
}
else if (e=='{'&&ch=='}')
{
return 1;
}
else
{
return 0;
}}
</pre>
算术表达式计算问题
中缀表达式和后缀表达式的描述
在编译系统中，算术表达式可以分为三类：算术表达式，关系表达式，逻辑表达式。任何一个算术表达式都是由：操作数，运算符和分界符组成。我们把操作数，运算符和分界符（分界符标志了一个算术表达式的结束）称为一个算术表达式的单词。
中缀表达式：算术表达式中的运算符总是出现在两个操作数之间（除单目运算符外）
A+（B-C/D）*E
后缀表达式：表达式中的运算符出现在操作数之后。编译系统对于中缀表达式处理方法是将其变成后缀表达式
ABCD/-E*+
后缀表达式的特点
后缀表达式的操作数和中缀表达式的操作数先后次序完全相同（上面ABCDE），只是运算符的先后次序改变了（+-/*）；
后缀表达式中没有括号，后缀表达式的运算次序就是其执行次序
后缀表达式的实现过程
编译系统设置一个存放运算符的堆栈，初始时栈顶置一个分界符“#”。编译系统从左到右依次扫描中缀表达式数据结构中的堆栈，每读到一个操作数就把它作为后缀表达式的一部分输出数据结构中的堆栈，每读到一个运算符（分界符也看作运算符）就将其优先级与栈顶运算符优先级运算符进行比较，以决定是就所读到的运算符进栈，还是将栈顶运算符作为最为后缀算术表达式的一部分输出。
运算符优先级别注意：若把O1看成栈顶运算符，O2看成当前扫描读到的运算符。
当O1为“+”或“-”，O2为“*”或“/”时，O1的优先级 < O2的优先级(满足先乘除数据结构中的堆栈 数据结构之堆栈（二），后加减)
当O1为“+”“-”“*”或“/”，O2为“（”时，O1的优先级 < O2的优先级（满足先括号内，后括号外的规则）
当O1的运算符和O2的运算符同级别时，O1的优先级 > O2的优先级别（同级别先左后右规则）
由于后缀表达式无括号，当O1为“（”，O2为“）”时，用标记“=”使算法在此时去掉该对算法；
当O1为“#”时，O2为“#”时，用标记“=”使算法在此时结束处理
若表中的值为空，则不允许出现这种情况，一旦出现即为中缀算术表达式语法出错，如O1为“）”，而O2为“（”情况，即为中缀表达式语法错误！
算法步骤：
（1）设置一个堆栈，初始时将栈顶元素置为#
（2）顺序读入中缀算术表达式，当读到的单词为操作数是就将其输出，并接着读下一个单词
（3）单读到的单词为运算符时，令a为当前栈顶运算符的变量，b为当前扫描读到运算符的变量，把当前读到的运算符赋给b,然后比较变量a的优先级和b的优先级。若a的优先级高于ｂ的优先级，则将ａ退栈并作为后缀表达式的一个单词输出，，然后比较新的栈顶元素运算符ａ的优先级与ｂ的优先级。
若优先级ａ＜ｂ，则将ｂ的值进栈，然后接着读下一个单词
若优先级ａ＞ｂ，则将ａ退栈并作为后缀表达式的一个单词输出，然后比较新的栈顶元素运算符ａ的优先级与ｂ的优先级。
若优先级ａ＝ｂ且ａ为“（”，ｂ为“）”。则将ａ退栈，接着读下一个单词
若优先级ａ＝ｂ且ａ为“＃”，ｂ为“＃”。算法结束。
函数实现
<pre class="cm-s-default" style="color:rgb( 89 , 89 , 89 );margin:0px;padding:0px;background-image:none;background-attachment:scroll;background-color:rgba( 0 , 0 , 0 , 0 );background-position:0% 0%;background-repeat:repeat repeat">int PostExp(char str[]) //借助堆栈计算后缀表达式str的值
{
DataType x,x1,x2;
int i;
LsNode *head; //定义头指针变量head
StackInitiate(&head); //初始化链式堆栈head
for(i-0;str[i]!=#;i++) //循环直到输入为#
{
if(isdigit(str[i])) //当str[i]为操作数时
{
x=(int)(str[i]-48); //转换成int类型数据存于变量x中
StackPush(head,x); //x入栈
}
else //当str[i]为运算符时
{
StackPop(head,&x2); //退栈的操作数，存于变量x2中
StackPop(head,&x1); //退栈的被操作数，存于变量x1中
switch(str[i]) //执行str[i]所表示的运算
{
case '+':
{
x1+=x2; break;
}
case '-':
{
x1-=x2; break;
}
case '*':
{
x1*=x2; break;
}
case '/':
{
if(x2==0.0)
{
printf("除数为0错误！\n");
exit(0);
}
else
{
x1/=x2;
break;
}
}
}
StackPush(head,x1); //运算结果入栈
}
}
StackPop(head,&x); //得到计算结果存于x
return x; //返回计算结果}
</pre>
应用
设有后缀算术表达式ABCD/-E*+，其中，变量A等于3，变量B等于6，变量C等于4，变量D等于2，变量E等于5，设计一个程序，求出该后缀算术表达式的值。
代码实现
<pre class="cm-s-default" style="color:rgb( 89 , 89 , 89 );margin:0px;padding:0px;background-image:none;background-attachment:scroll;background-color:rgba( 0 , 0 , 0 , 0 );background-position:0% 0%;background-repeat:repeat repeat">#include
include //包含有exit()函数
include //包含isdigit()函数
include //定义DataType（）函数
typedef int DataType;
include"LinStack.h"
int PostExp(char str[]) //借助堆栈计算后缀表达式str的值
{
DataType x,x1,x2;
int i;
LsNode *head; //定义头指针变量head
StackInitiate(&head); //初始化链式堆栈head
for(i-0;str[i]!=#;i++) //循环直到输入为#
{
if(isdigit(str[i])) //当str[i]为操作数时
{
x=(int)(str[i]-48); //转换成int类型数据存于变量x中
StackPush(head,x); //x入栈
}
else //当str[i]为运算符时
{
StackPop(head,&x2); //退栈的操作数，存于变量x2中
StackPop(head,&x1); //退栈的被操作数，存于变量x1中
switch(str[i]) //执行str[i]所表示的运算
{
case '+':
{
x1+=x2; break;
}
case '-':
{
x1-=x2; break;
}
case '*':
{
x1*=x2; break;
}
case '/':
{
if(x2==0.0)
{
printf("除数为0错误！\n");
exit(0);
}
else
{
x1/=x2;
break;
}
}
}
StackPush(head,x1); //运算结果入栈
}
}
StackPop(head,&x); //得到计算结果存于x
return x; //返回计算结果}
void main()
{
char str[]="3642/-5*+#";
int result;
result=PostExp(str);
printf("后缀算术表达式计算结果为：%d",result);}
</pre>
程序运行结果：23