(三)1.1_中缀式转化为后缀式并求值
一.问题描述
输入一串中缀式,将其转化为后缀式,并利用该后缀式计算出算式的结果.
例如:
输入的中缀式为2*(4-2)+6/3;
转化为后缀式为242-*63/+;
计算结果为6;
二.思路分析
我们先从键盘中输入中缀式(以’#‘开始和结束,为了方便后面的操作);然后把中缀式存入顺序表La中
1.中缀式转化为后缀式算法概述
先构建一个存储运算符的栈,和一个存储后缀式的顺序表Lb.刚开始把顺序b中的第一个元素’#‘入栈,然后循环遍历中缀式顺序表La(从第2个元素开始),如果遍历到的是运算数,则直接把这个数存到后缀式顺序表Lb中,如果遍历到的是运算符,这时我们就要让它和栈顶的运算符元素进行优先权的比较;
①如果是栈顶元素的优先权更小,则该元素入栈,遍历继续往下走,
②如果是优先权相等,则说明是左括号匹配到了右括号,出栈一个元素,遍历往下走(脱括号处理),
③如果是栈顶元素的优先权更大,则出栈一个元素,并把出栈的元素存到后缀式顺序表Lb中,但遍历位置不动,因为下次循环的栈顶元素要与该位置的元素进行优先权比较(这个元素还没存到后缀式顺序表中呢,怎么能丢了呢…)
就这样获取栈顶元素进行比较,一直循环遍历到顺序表最后一个元素’#‘且栈内只剩下’#’,最后顺序表Lb中存储的就是后缀式了.
2.后缀式计算求值算法概述
通过上面的算法,我们得到了一个存储了后缀式的顺序表Lb,我们构建一个存储运算数的栈,然后我们对后缀式的顺序表Lb进行遍历,
①如果遍历到的是运算数,则该元素入栈,遍历继续往下走
②如果遍历到的是运算符,则从栈内出栈两个数,并利用这个运算符进行运算,把得到的结果入栈,然后遍历继续往下走.
注意:强调一下运算顺序,假如运算符是-,元素a先出栈,b后出栈,则运算顺序是b-a
就这样循环遍历,直到后缀式顺序表Lb中的元素都被遍历完,栈内剩下的那个唯一的数,就是运算结果
三.代码实现
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"SqStack.h"
#define LISTMAXSIZE 100
//设置运算符的优先级,优先级大于,小于,等于,不能比较分别用1,-1,0,-2表示
int compare[7][7]=
{
// + - * / ( ) #
/* + */ { 1, 1, -1, -1, -1, 1, 1},
/* - */ { 1, 1, -1, -1, -1, 1, 1},
/* * */ { 1, 1, 1, 1, -1, 1, 1},
/* / */ { 1, 1, 1, 1, -1, 1, 1},
/* ( */ {-1,-1, -1, -1, -1, 0,-2},
/* ) */ { 1, 1, 1, 1, -2, 1, 1},
/* # */ {-1,-1, -1, -1, -1,-2, 0}
};
//比较运算符优先级
int Precede(char c1,char c2)
{
//根据符号分配一下数组下标
int pos1,pos2;
switch(c1)
{
case '+': pos1=0; break;
case '-': pos1=1; break;
case '*': pos1=2; break;
case '/': pos1=3; break;
case '(': pos1=4; break;
case ')': pos1=5; break;
case '#': pos1=6; break;
}
switch(c2)
{
case '+': pos2=0; break;
case '-': pos2=1; break;
case '*': pos2=2; break;
case '/': pos2=3; break;
case '(': pos2=4; break;
case ')': pos2=5; break;
case '#': pos2=6; break;
}
return compare[pos1][pos2];
}
//判断是不是运算符
bool IsOP(char ch)
{
switch(ch)
{
case '+': return true;
case '-': return true;
case '*': return true;
case '/': return true;
case '(': return true;
case ')': return true;
case '#': return true;
default : return false;
}
}
typedef char ElemType;
typedef struct //顺序表
{
ElemType *elem;
int length;
int size;
}SqList;
void InitList(SqList *L) //初始化顺序表
{
L->elem=(ElemType*)malloc(LISTMAXSIZE*sizeof(ElemType)); //分配存储空间
L->length=0;
L->size=LISTMAXSIZE;
}
void DestoryList(SqList *L)
{
free(L->elem);
}
void CreateInfixExpression(SqList *L) //输入中缀式
{
ElemType e;
int pos=0;
e=getchar();
L->elem[L->length++]=e; //为了将输入'#'字符存入顺序表
do
{
e=getchar();
L->elem[L->length++]=e; //将输入的字符存入顺序表
} while(e!='#'&&L->length<L->size); //当输入'#'(不包括第一个元素)或顺序表已满则输入结束
}
void PrintList(SqList *L)
{
for(int pos=0;pos<=L->length-1;pos++)
{
printf("%c",L->elem[pos]);
}
}
//中缀式转化为后缀式
void InversePolandExpression(SqList* Exp_a,SqList *Exp_b)
{
//Exp_a是原来存储中缀式的顺序表,Exp_b是用来存储后缀式的顺序表
int pos1=0,pos2=0; //Exp_a,Exp_b顺序表的位置下标
SqStack<char> OPTR; //存储运算符的栈
InitStack(&OPTR,20);
Push(&OPTR,Exp_a->elem[pos1++]); //符号'#'入栈
char e,x;
GetTop(&OPTR,e);
while(Exp_a->elem[pos1]!='#'||e!='#') //当中缀式顺序表中还有元素或者运算符栈中还有元素时循环进行
{
//原理: 只有操作符栈中栈顶元素遇到优先级小于它的元素,才会把该运算符插入顺序表,
//这样就有了两个运算符,而上一个运算符优先级是更高的,肯定要先进行运算
if(!IsOP(Exp_a->elem[pos1])) //如果不是运算符,即是运算数
{
Exp_b->elem[pos2++]=Exp_a->elem[pos1++]; //则直接存入后缀式顺序表中
Exp_b->length++;
}
else //如果是运算符
{
GetTop(&OPTR,e); //读取运算符栈的栈顶元素,和遍历到的运算符做优先级比较
switch(Precede(e,Exp_a->elem[pos1]))
{
case -1: //如果栈顶运算符元素优先级小于遍历到的运算符元素
{
Push(&OPTR,Exp_a->elem[pos1++]); //将中缀式运算符元素存入运算符栈
} break;
case 0: //如果栈顶运算符元素优先级等于遍历到的运算符元素
{
Pop(&OPTR,x); //优先级相等,说明是(),进行配对消除处理
pos1++;
} break;
case 1: //如果栈顶运算符元素优先级大于遍历到的运算符元素
{
Pop(&OPTR,x); //将栈顶运算符元素存入后缀式顺序表,但中缀式顺序表遍历位置不移动,还要再次用来比较
Exp_b->elem[pos2++]=x;
Exp_b->length++;
} break;
}//switch
GetTop(&OPTR,e); //栈顶元素发生了改变,所以要重新获取一下
}//else
}//while
DestoryStack(&OPTR);
}
//计算逆波兰式
float CalculatePolandExpression(SqList* Exp)
{
//原理:遇到运算符就从栈中弹出两个数进行运算,结果在压入栈中
SqStack<float> OPND; //存放运算数的栈
InitStack(&OPND,20);
int pos=0;
float num1,num2,sum;
while(pos<=Exp->length-1)
{
if(!IsOP(Exp->elem[pos])) //如果遍历到后缀式的元素是操作数
{
Push(&OPND,(float)(Exp->elem[pos++]-'0')); //字符类型减去'0'转化为数字类型,将操作数得到的结果压入栈中
}
else //如果遍历到后缀式的元素是操作符
{
Pop(&OPND,num2); //出栈两个数进行运算
Pop(&OPND,num1);
switch(Exp->elem[pos++])
{
case '+': sum=num1+num2; break;
case '-': sum=num1-num2; break;
case '*': sum=num1*num2; break;
case '/': sum=num1/num2; break;
}
Push(&OPND,sum); //将计数得到的结果压入栈中
}//else
}//while
float x;
Pop(&OPND,x); //最后栈顶元素就是结果
DestoryStack(&OPND);
return x;
}
int main()
{
SqList Exp_a,Exp_b; //构建两个顺序表,分别存储中缀式和后缀式(逆波兰式)
InitList(&Exp_a);
InitList(&Exp_b);
printf("请输入要计算的中缀式(以'#'表示开始和结束):\n");
CreateInfixExpression(&Exp_a); //输入中缀式
InversePolandExpression(&Exp_a,&Exp_b); //转换为逆波兰式
printf("\n后缀式为:\n");
PrintList(&Exp_b);
float result;
result=CalculatePolandExpression(&Exp_b); //计算逆波兰式
printf("\nresult=%f",result);
DestoryList(&Exp_a); //销毁顺序表
DestoryList(&Exp_b);
return 0;
}
操作结果
四.相关提示
1.用数组保存了运算符之间的优先权关系
2.该算法只能计算0~9之间的数,假如输入大于等于10的数,因为无法识别是两个数还是一个数,所以无法计算,例如输入10*(12-3),这个式子是算不出的.
3.代码里的栈是用我自己写的一个栈模板头文件里的,这里没有附上其头文件,故代码在读者电脑上无法直接运行.读者需替换成自己创建的栈即可.