数据结构（括号匹配与表达式计算）
目录
括号配对
括号匹配算法
表达式计算
后缀式的计算
中缀式转后缀式
括号配对
编译器做语法检查的任务之一是检查符号是否配对，最简单的符号匹配问题是括号是否匹配，如开括号( 及{ 后面必须依次跟随相应的闭括号 }及 )。
如下段程序中的括号、引号是否匹配。
int main()
{ int a[20], i;
for (i=0; i<20; i++)
{ a[i]=3*(19-i)/5*(12-6);
cout<<a[i]<<'/t';
}
return 0;
}括号匹配算法
1.首先创建一个字符栈。
2.从源程序中读入字符。
如果读入的是开括号，将其进栈。
如果读入的是闭括号但栈是空的，说明少开括号，报错并结束。
如果读入的是闭括号但栈不空，将栈中的开括号出栈。如果出栈的开括号和读入的闭 括号不是同种类型（如一个为小括号，一个为中括号），说明不匹配，报错并结束。
3.继续从文件中读入下一个符号，非结束符则转向2)，否则转向4)。
4.如果栈非空，说明开括号多了，报错并结束；
5.否则括号配对成功，结束。
核心而简单的算术表达式中括号匹配检测程序：（此处引入了链式栈）
#include <iostream>
#include "linkStack.h"
using namespace std;
int main()
{ char str[20];
linkStack<char> s; //建立一个字符栈
char ch;
int i;
cout<<"Input the string: ";
cin.getline(str, 20, '\n');
cout<<"str: "<<str<<endl;
i=0; ch=str[i++];
while (ch!='\0')
{ switch(ch)
{ case '(': s.push(ch); break;
case ')': if (s.isEmpty())
{ //读入一个闭括号，栈却空，找不到匹配的开括号
cout<<"An opening bracket '(' is expected!\n";
return 1;
}
else s.pop();
break;
}
ch=str[i++];
}
if (!s.isEmpty()) //式子读入结束，发现栈中还有多余的开括号
cout<<"A closing bracket ')' is expected!\n";
return 0;
}
（为简化，假设只有小括号）
表达式计算
算术表达式是编程语言中一个最基本的组成元素，由操作数、运算符及括号构成。
以下分析中，为了简化，限定操作数为一位整数；运算符为加、减、乘、除四种二元运算符；括号仅含有小括号，如：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<int> 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<char> s; //用字符栈 int i,j; char topCh;
s.push('#'); //铺垫一个底垫 i=0;j=0
while (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;
}//switch
i++;
}//else
}//while
//将栈中还没有弹出的操作符弹空
topCh = s.top();
while (topCh!='#')
{ sufStr[j++] = topCh;
s.pop();
topCh = s.top();
}
sufStr[j]='\0'; //后缀字符串加结束符'\0'
}