数据结构（括号匹配与表达式计算）
目录
括号配对
括号匹配算法
表达式计算
后缀式的计算
中缀式转后缀式
括号配对
编译器做语法检查的任务之一是检查符号是否配对，最简单的符号匹配问题是括号是否匹配，如开括号( 及{ 后面必须依次跟随相应的闭括号 }及 )。
如下段程序中的括号、引号是否匹配。
int main()
{ int a[20], i;for (i=0; i<20; i++){ a[i]=3*(19-i)/5*(12-6);cout<括号匹配算法
1.首先创建一个字符栈。 2.从源程序中读入字符。 如果读入的是开括号，将其进栈。 如果读入的是闭括号但栈是空的，说明少开括号，报错并结束。如果读入的是闭括号但栈不空，将栈中的开括号出栈。如果出栈的开括号和读入的闭 括号不是同种类型（如一个为小括号，一个为中括号），说明不匹配，报错并结束。
3.继续从文件中读入下一个符号，非结束符则转向2)，否则转向4)。 4.如果栈非空，说明开括号多了，报错并结束； 5.否则括号配对成功，结束。核心而简单的算术表达式中括号匹配检测程序：（此处引入了链式栈）
#include
#include "linkStack.h"
using namespace std;int main()
{ char str[20];linkStack s; //建立一个字符栈char ch;int i;cout<<"Input the string: ";cin.getline(str, 20, '\n');cout<<"str: "< （为简化，假设只有小括号）
表达式计算
算术表达式是编程语言中一个最基本的组成元素，由操作数、运算符及括号构成。
以下分析中，为了简化，限定操作数为一位整数；运算符为加、减、乘、除四种二元运算符；括号仅含有小括号，如：5*(7-2*3)+8/2。
算术表达式中运算符出现在两个操作数之间，这种形式称为中缀式，运算符在前称为前缀式或波兰式，运算符在后称后缀式或逆波兰式。
中缀式有利于人的理解，但不便于计算机处理；
前缀式不便于人理解，但可去掉括号；
后缀式不便于人理解，可去掉括号，更便于计算机计算。
在编译时，编译器首先要把中缀式转换成后缀式。
表达式计算涉及到两个方面的工作：
中缀式转换为后缀式 后缀式计算如，表达式5*(7-2*3)+8/2转换为后缀式为： 5 7 2 3*-*8 2/+。
手工转换时，先计算的先转换。
可以看出：
从左至右，操作数保持原来的相对位置，操作符是先计算的先出现。
后缀式经过一次从左到右的扫描即可计算出结果。
后缀式的计算
如，表达式5*(7-2*3)+8/2转换为后缀式为： 5 7 2 3*-*8 2/+。
手工转换时，先计算的先转换。
在后缀式中可以看出：
从左至右，操作数保持原来的相对位置，操作符是先计算的先出现。
计算后缀式：
1.声明一个操作数栈，依次读入后缀式中的字符。 2.若读到的是操作数，将其进栈； 3.若读到的是运算符，将栈顶的两个操作数出栈。后弹出的操作数为被操作数，先弹出的 为操作数。将出栈的两个操作数完成运算符所规定的运算后将结果进栈。 4.继续读入后缀式中的字符，如上处理，最后直到后缀式中所有字符读入完毕。 5.当完成以上操作后，栈中只剩一个操作数，弹出该操作数，它就是表达式的计算结果。计算后缀式： 以5 7 2 3*-*8 2/+为例（逐步进行分析）
计算后缀式算法实现
int calcPost(char *sufStr)
{ int op1, op2, op; int tmp, i; linkStack s;i=0;while (sufStr[i]!='\0'){ if ((sufStr[i]>='0')&&(sufStr[i]<='9')) //数字转为整数后进栈{ tmp = sufStr[i] - '0';s.push(tmp);}else{ op2 = s.top(); s.pop(); //栈顶整数出栈 op1 = s.top(); s.pop();switch (sufStr[i]){ case '*': op = op1*op2; break; //如果是运算符为'*',则做*运算case '/': op = op1/op2; break;case '+': op = op1+op2; break;case '-': op = op1-op2; break; };s.push(op); //每一步计算结果进栈} i++;} op = s.top(); s.pop();return op; }
从算法中可以看出，对后缀式字符串从左到右一次扫描即可计算完毕。
中缀式转后缀式
表达式5*(7-2*3)+8/2转换为后缀式为： 5 7 2 3*-*8 2/+。
手工转换时，先计算的先转换，即按照计算的优先级来。
观察后缀式，可以看出：
从左至右，操作数保持原来的相对位置，操作符是先计算的先出现。
中缀式转后缀式算法分析：
Ø对一个中缀表达式，从左至右顺序读入各操作数、运算符。 Ø当读入的是操作数时，直接输出 (如：输出到屏幕或追加到保存后缀式的字符串中)； Ø当读入的是操作符时，当读入的运算符优先级高时，因不知是否后续读入的操作符优先级更高，只能将本次读入的运算符暂存，继续读入中缀式。当读入的运算符优先级低时，才可能计算刚才暂存的运算符(即输出)；在暂存机构中，越是后面存入的操作符，优先级越高，越先出来进行计算，这种结构就是栈，处于栈顶的运算符的优先级最高。 Ø相同运算符，先进栈的优先级高于后进栈的。 Ø表达式中的括号也可以看作是一种操作符，其中开括号具有两面性：即将进入栈的开括号，优先级最高；已经在栈顶的开括号，优先级最低。括号在后缀式中是要消失的，消失靠闭括号。当读入一个闭括号时，计算之前进栈的运算符，直到遇到一个开括号，然后开闭括号双双消失即可。中缀式转后缀式算法：
对一个中缀表达式，从左至右顺序读入各操作数、运算符。
Ø当读入的是操作数时，直接输出 。 Ø当读入的符号是开括号，直接进栈。 Ø当读入的符号是闭括号，反复进行栈顶元素出栈、输出，直到弹栈的是开括号。 Ø当读入的是操作符时，如果栈顶操作符的优先级更高，反复弹栈、输出直到栈顶元素优先级低于读入操作符的优先级，读入操作符压栈；如果栈顶操作符的优先级低，读入的运算符进栈。中缀式转后缀式算法示例：5*(7-2*3)+8/2转换为 5 7 2 3*-*8 2/+
设立一个用于保存运算符的堆栈，先将一个底垫’#’压栈，设其优先级为最低。
void inToSufForm(char *inStr, char *sufStr)
{ linkStack s; //用字符栈 int i,j; char topCh;s.push('#'); //铺垫一个底垫 i=0;j=0while (inStr[i]!='\0'){ if ((inStr[i]>='0')&&(inStr[i]<='9'))sufStr[j++]=inStr[i++];else { switch (inStr[i]){ case '(': s.push('('); break; //优先级最高，直接入栈case ')': //弹栈，弹出元素进入后缀式，直到弹出一个左括号topCh = s.top(); s.pop();while (topCh!='('){ sufStr[j++] = topCh;topCh = s.top(); s.pop();}//')'字符不入栈break;case '*':case '/': topCh = s.top();while ((topCh=='*')||(topCh=='/'))//*、/为左结合，故后来者优先级低{ s.pop();sufStr[j++] = topCh;topCh = s.top();}s.push(inStr[i]); break;case '+':case '-': topCh = s.top();while ((topCh!='(')&&(topCh!='#'))//只有左括号和底垫优先级比+、-低{ s.pop(); sufStr[j++] = topCh; topCh = s.top(); }s.push(inStr[i]);break;}//switchi++;}//else}//while//将栈中还没有弹出的操作符弹空topCh = s.top();while (topCh!='#'){ sufStr[j++] = topCh;s.pop();topCh = s.top();}sufStr[j]='\0'; //后缀字符串加结束符'\0'
}