3. 把中缀表达式转换为后缀表达式的算法
设以’@’字符作为结束符的中缀算术表达式已经保存在s1字符串中，转换后得到的后缀算术表达式拟存于s2字符串中。由中缀表达式转换为后缀表达式的规则可知：转换前后，表达式中的数值项的次序不变，而运算符的次序发生了变化，由处在两个运算对象的中间变为处在两个运算对象的后面，同时去掉了所有的括号。为了使转换正确，必须设定一个运算符栈，并在栈底放入一个非凡算符，假定为’@’字符，让它具有最低的运算符优先级，假定为数值0，此栈用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符，待它的两个运算对象都放入到后缀表达式以后，再令其出栈并写入到后缀表达式中。
把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。若碰到的是空格则认为是分隔符，不需要进行处理；若碰到的是数字或小数点，则直接写入到s2中，并在每个数值的最后写入一个空格；若碰到的是左括号，则应把它压入到运算符栈中，待以它开始的括号内的表达式转换完毕后再出栈；若碰到的是右括号，则表明括号内的中缀表达式已经扫描完毕，把从栈底直到保存着的对应左括号之间的运算符依次退栈并写入s2串中；若碰到的是运算符，当该运算符的优先级大于栈顶运算符的优先级（加减运算符的优先级设定为1，乘除运算符的优先级设定为2，在栈中保存的非凡运算符’@’和’(’的优先级设定为0)时，表明该运算符的后一个运算对象还没有被扫描并放入到s2串中，应把它暂存于运算符栈中，待它的后一个运算对象从s1串中读出并写入到s2串中后，再另其出栈并写入s2串中；若碰到的运算符的优先级小于等于栈顶运算符的优先级，这表明栈顶运算符的两个运算对象已经被保存到s2串中，应将栈顶运算符退栈并写入到s2串中，对于新的栈顶运算符仍继续进行比较和处理，直到被处理的运算符的优先级大于栈顶运算符的优先级为止，然后另该运算符进栈即可。
按照以上过程扫描到中缀表达式结束符’@’时，把栈中剩余的运算符依次退栈并写入到后缀表达式中，再向s2写入表达式结束符’@’和字符串结束符’\0’，整个转换过程就处理完毕，在s2中就得到了转换成的后缀表达式。
例如，设中缀算术表达式s1为：10+(18+9*3)/15-6@，使用的运算符栈用R表示，则转换过程如下：
（1）开始时存放后缀表达式的字符串s2为空，R中压入有’@’算符，它具有最低的优先级0：
@
（2）当扫描到s1中的左括号时，s2和R中的数据变化如下：
1 0
@ + (
（3）当扫描到s1中的数值3时，s2和R中的数据变化为：
1 0 1 8 9 3
@ + ( + *
（4）当扫描到s1中的右括号时，s2和R变为：
1 0 1 8 9 3 * +
@ +
（5）当扫描到s1中的数值15时，s2和R又变为：
1 0 1 8 9 3 * + 1 5
@ + /
（6）当扫描到s1中的’@’字符时，s2和R为：
1 0 1 8 9 3 * + 1 5 / + 6
@ -
1 0 1 8 9 3 * + 1 5 / + 6 - @ Ù
（7）当整个处理过程结束后，R栈为空，s2为：
将中缀算术表达式转换为后缀算术表达式的算法描述如下：
void Change(char* s1, char* s2)
// 将字符串s1中的中缀表达式转换为存于字符串s2中的后缀表达式
{
Stack R; // 定义用于暂存运算符的栈
InitStack(R); // 初始化栈
Push(R,'@'); // 给栈底放入'@'字符，它具有最低优先级0
int i,j;
i=0; // 用于指示扫描s1串中字符的位置，初值为0
j=0; // 用于指示s2串中待存字符的位置，初值为0
char ch=s1[i]; // ch保存s1串中扫描到的字符，初值为第一个字符
while(ch!='@')
{ // 顺序处理中缀表达式中的每个字符
if(ch==' ')
// 对于空格字符不做任何处理，顺序读取下一个字符
ch=s1[++i];
else if(ch=='(')
{ // 对于左括号，直接进栈
Push(R,ch);
ch=s1[++i];
}
else if(ch==')')
{ // 对于右括号，使括号内的仍停留在栈中的运算符依次
// 出栈并写入到s2中
while(Peek(R)!='(')
s2[j++]=Pop(R);
Pop(R); // 删除栈顶的左括号
ch=s1[++i];
}
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
{ // 对于四则运算符，使暂存在栈中的不低于ch优先级
// 的运算符依次出栈并写入到s2中
char w=Peek(R);
while(Precedence(w)>=Precedence(ch))
{ // Precedence(w)函数返回运算符形参的优先级
s2[j++]=w;
Pop(R); w=Peek(R);
}
Push(R,ch); // 把ch运算符写入栈中
ch=s1[++i];
}
else
{ // 此处必然为数字或小数点字符
while(isdigit(ch)||ch=='.')
{ // 把一个数值中的每一位依次写入到s2串中
s2[j++]=ch;
ch=s1[++i];
}
s2[j++]=' '; // 被转换后的每个数值后放入一个空格
}
}
// 把暂存在栈中的运算符依次出栈并写入到s2串中
ch=Pop(R);
while(ch!='@') {
if(ch=='(') {
cerr<<"expression error!"<<endl;
exit(1);
}
else {
s2[j++]=ch;
ch=Pop(R);
}
}
// 在后缀表达式的末尾放入表达式结束符和字符串结束符
s2[j++]='@';
s2[j++]='\0';
}
求运算符优先级的Precedence函数为：
int Precedence(char op)
// 返回运算符op所对应的优先级数值
{
switch(op)
{
case '+':
case '-':
return 1; // 定义加减运算的优先级为1
case '*':
case '/':
return 2; // 定义乘除运算的优先级为2
case '(':
case '@':
default:
return 0; // 定义在栈中的左括号和栈底字符的优先级为0
}
}
在转换算法中，中缀算术表达式中的 每个字符均需要扫描一遍，对于扫描到的每个运算符，最多需要进行入栈、出栈和写入后缀表达式这三次操作，对于扫描到的数字或小数点，只需要把它直接写入到后缀表达式即可。所以，此算法的时间复杂度为O(n)，n为后缀表达式中字符的个数。该算法需要使用一个运算符栈，需要的深度不会超过中缀表达式中运算符的个数，所以此算法的空间复杂度至多也为O(n)。
利用表达式的后缀表示和堆栈技术只需要两遍扫描就可完成中缀算术表达式的计算，显然比直接进行中缀算术表达式计算的扫描次数要少得多。
在上述讨论的中缀算术表达式求值的两个算法中，把中缀表示转换为后缀表示的算法需要使用一个字符栈，而进行后缀表达式求值的算法又需要使用一个浮点数栈，这两个栈的元素类型不同，所以栈的类型无法作为全局量来定义，栈运算的函数也无法适应这种要求。为了解决这个问题，必须把Stack栈类型定义为模板类，把栈运算的函数定
义为该类的公用成员函数，通过调用成员函数来实现栈的运算。这里对此不作深入讨论，留给读者作为练习。
假定采用类模板来定义Stack类和编写计算中缀算术表达式值的程序，若执行下面的主程序：
void main()
{
char a[30];
char b[30];
cout<<"请输入一个以'@'字符结束的中缀算术表达式："<<endl;
cin.getline(a,sizeof(a)); // 从键盘上输入一行表示中缀算术表达
// 式的字符串存入到字符数组a中
Change(a,b);
cout<<"对应的后缀算术表达式为："<<endl;
cout<<b<<endl;
cout<<"求值结果为："<<Compute(b)<<endl;
}
则得到的显示结果如下：
请输入一个以'@'字符结束的中缀算术表达式：
12+(3*(20/4)-8)*6@
对应的后缀算术表达式为：
12 3 20 4 /*8 -6 *+@
求值结果为：54
三、队列
1． 队列的定义
队列（Queue）简称队，它也是一种运算受限的线性表，其限制是仅答应在表的一端进行插入，而在表的另一端进行删除。我们把进行插入的一端称作队尾(rear)，进行删除的一端称作队首(front)。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为离队或出队，元素离队后，其后继元素就成为队首元素。由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进入的次序离队，所以又把队列称为先进先出表（First In First Out, 简称FI
FO）。
在日常生活中，人们为购物或等车时所排的队就是一个队列，新来购物或等车的人接到队尾(即进队)，站在队首的人购到物品或上车后离开(即出队)，当最后一人离队后，则队列为空。
例如，假定有a,b,c,d四个元素依次进队，则得到的队列为(a,b,c,d)，其中字符a为队首元素，字符d为队尾元素。若从此队中删除一个元素，则字符a出队，字符b成为新的队首元素，此队列变为(b,c,d)；若接着向该队列插入一个字符e，则e成为新的队尾元素，此队列变为(b,c,d,e)；若接着做三次删除操作，则队列变为(e)，此时只有一个元素e，它既是队首元素又是队尾元素，当它被删除后队列变为空。
2. 队列的存储结构
队列的存储结构同线性表和栈一样，既可以采用顺序结构，也可以采用链接结构。
(1) 队列的顺序存储结构
队列的顺序存储结构需要使用一个数组和两个整型变量来实现，利用数组来顺序存储队列中的所有元素，利用两个整型变量来分别存储队首元素和队尾元素的下标位置，分别称它们为队首指针和队尾指针。假定存储队列的数组用queue[QueueMaxSize]表示，队首和队尾指针分别用front和rear表示，则元素类型为ElemType的队列的顺序存储类型可定义为：
ElemType queue[QueueMaxSize];
int front, rear;
其中QueueMaxSize为一个整型全局常量，需事先通过const语句定义，由它确定顺序队列（即顺序存储的队列）的最大长度，即最多能够存储的元素个数。当然，队列的顺序存储空间也可以采用动态分配，此时用于决定最大长度的量可以为全局常量，也可以为全局或局部变量。如在一个函数的函数体中使用下面语句能够为一个队列分配长度为n的数组空间，该数组名仍用queue表示。
ElemType* queue=new ElemType[n];
队列的顺序存储类型同样可以用一个记录类型来表示，假定记录类型名为Queue，则该类型定义为:
struct Queue {
ElemType queue[QueueMaxSize];
int front, rear;
};
假定一个队列的当前状态如图4-10(a)所示，此时已经有a,b,c三个元素相继出栈（为了同队列中的元素相区别，把它们分别括了起来），队首指针front的值为3，指向的队首元素为d，队尾指针的值为7，指向的队尾元素为h；若接着插入一个新元素i，则队列的当前状态如图4-10(b)所示；若再接着删除一个元素，则变为图4-10(c)所示。
0 1 2 3 4 5 6 7 8 QueueMaxSize-1
(a) (b) (c) d e f g h
front rear
(a)
0 1 2 3 4 5 6 7 8 QueueMaxSize-1
(a) (b) (c) d e f g h i
front rear
(b)
0 1 2 3 4 5 6 7 8 QueueMaxSize-1
(a) (b) (c) (d) e f g h i
front rear
(c)
图4-10 顺序队列的插入和删除操作示意图
| Word教程网 | Excel教程网 | Dreamweaver教程网 | Fireworks教程网 | PPT教程网 | FLASH教程网 | PS教程网 |
| HTML教程网 | DIV CSS教程网 | FLASH AS教程网 | ACCESS教程网 | SQL SERVER教程网 | C语言教程网 | JAVASCRIPT教程网 |
| ASP教程网 | ASP.NET教程网 | CorelDraw教程网 |
QQ：2693987339(点击联系)购买教程光盘
:
