数据结构实验三后缀表达式的计算

实验三 后缀表达式的计算

实验目的：

熟练掌握栈和队列的存储结构设计及基本操作的实现；学会分析实际问题中具有栈特点的数据结构；了解表达式的前缀、中缀、后缀等计算机内表示形式。 实验内容与要求：

按常规形式输入算术表达式（例如：输入2*(6-4)+8/4），要求能够： （1）生成表达式的后缀表示，并输出； （2）生成表达式的前缀表示，并输出；

（3）基于表达式的后缀表示，对该表达式求值； （4）编写一个主程序对表达式求值函数进行测试。 算法设计：

#include<stdio.h> 关系，在分析过程查找到这个值，表示表达#include<malloc.h> 式有错。 #include<string.h> char *OpretorS="+-*/()#"; //运算符集 #define ERROR 0 char *Express="2*(6-4)+8/4"; //初始化的#define OK 1 表达式 #define N 50 int InitStack(SqStack *S); //构造空栈 #define STACK_INT_SIZE 10 //存储空int push(SqStack *S,ElemType *e); //入间初始分配量 栈 #define Queue_Size 20 int Pop(SqStack *S); //出栈 typedef int ElemType; //定义元素的类型 void initQueue(SeqQueue *Q) //队列初typedef struct 始化 { { char Qdata[Queue_Size]; Q->front=0; int front,rear; Q->rear=0; }SeqQueue; } typedef struct int EnterQueue(SeqQueue *Q,char c) //入{ 队 ElemType *base; { ElemType *top; if (Q->rear==Queue_Size)

{ int stacksize; //当前已分配的存储空

间 printf("\n队列满，无法入队！\n"); }SqStack; return ERROR; SqStack OPTR, OPND; } SeqQueue SeQ; Q->Qdata[Q->rear]=c; char PreTab[7][7]={ Q->rear++; {'>','>','<','<','<','>','>'}, return OK; {'>','>','<','<','<','>','>'}, } {'>','>','>','>','<','>','>'}, int OutQueue(SeqQueue *Q,char *e) //出 {'>','>','>','>','<','>','>'}, 队 {'<','<','<','<','<','=','x'}, { {'>','>','>','>','x','>','>'}, if(Q->front==Q->rear) {'<','<','<','<','<','x','='} { }; //该矩阵中，X字符表示不存在优先 printf("\n队列空，无法出队！\n");

1

return ERROR; }

*e=Q->Qdata[Q->front++]; return OK; }

int InitStack(SqStack *S) { S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType));

if(!S->base) return ERROR; S->top=S->base;

S->stacksize=STACK_INT_SIZE; return OK; }

int Push(SqStack *S,ElemType e) {

if ((S->top-S->base)>STACK_INT_SIZE) return 0;

*S->top=e; S->top++; return OK; }

int Pop(SqStack *S) { int e;

if (S->top==S->base) return 0; S->top--; e=*S->top; return *S->top;

} //判定c是否运算符，若是运算符则返回改运算符在运算符集中的位置 int IsOps(char c) { int i=0; char *p; p=OpretorS; while(i<7) { if (*p++==c) break; i++; }

return i; }

2

char Precede(char c1,char c2) //返回c1与c2运算符的优先关系 { int i,j;

i=IsOps(c1); j=IsOps(c2);

if ( PreTab[i][j]=='x') return 0; return PreTab[i][j]; }

int Operate(int a,char TheOp,int b) //进行TheOp计算 { switch(TheOp) { case'+':return a+b; case'-':return a-b; case'*':return a*b; case'/':return a/b; }

return 0; }

int f(char c) //判断运算符级别函数 { int f=-1; switch(c) {

case'+':

case'-':f=1;break; case'*':

case'/':f=2;break; default:f=0;break; }

return f; }

int Operator(char c) //判断字符是否为操作符 { if(c=='+'||c=='-'||c=='*'||c=='/') return 1; else return 0; }

void convert(char s[N]) //将中缀表达式转化为前缀表达式 { char p[N],stack[N];

int top=0,j=0, len=0; if(s[0]==')') { printf("算术表达式错误！"); printf("\n"); } else { while(s[len]!='\0') { len++; }

for(int i=len-1;i>=0;) { if(s[i]>=48&&s[i]<=57) { p[j]=s[i]; j++; }

if(s[i]==')') //假如是回括号，将它压栈。 {

top++;

stack[top]=s[i]; }

while(Operator(s[i])) {

if(top==0||stack[top]==')'||f(s[i])>=f(stack[top]))

{

top++;

stack[top]=s[i];break; } else {

p[j]=stack[top]; top--;j++; } }

if(s[i]=='(') //假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。 {

3

while(stack[top]!=')') {

p[j]=stack[top]; top--;j++; } top--; } i--; }

while(top!=0) //假如输入完毕，栈中剩余的所有操作符出栈并加到输入中 {

p[j]=stack[top]; j++; top--; }

p[j]='\0';

printf("\n前缀表达式为: "); for(;j>=0;j--) printf("%c",p[j]); printf("\n"); } }

int main() { char *ScanChar; char c1,c; char TheOp; int b,a,digit;

InitStack(&OPTR); Push(&OPTR,'#'); InitStack(&OPND); initQueue(&SeQ); ScanChar=Express; c=*ScanChar;

while(c!='#'||*OPTR.top!='#') { if (c==0) c='#';

if (IsOps(c)>=7) //判定是否是运算符，若IsOps的值>=7，则c是操作数 { digit=c-'0'; //将字符转换成相应的数值

Push(&OPND,digit); //操

作数入栈

EnterQueue(&SeQ,c); //操作数入队

c=*++ScanChar; } else { c1=*(OPTR.top-1);

switch(Precede(c1,c)) //调用哪个函数 { case'<':Push(&OPTR,c); c=*++ScanChar;break;

case'=':TheOp=Pop(&OPTR); if(c!=0&&c!='#') c=*++ScanChar;break; //脱括号 case'>':TheOp=Pop (&OPTR ); //参与计算的运算符出栈

EnterQueue(&SeQ,TheOp); //参与运算的运算符入队

b=Pop(&OPND);a=Pop(&OPND);

Push(&OPND,Operate(a,TheOp,b));break; default:printf("\n算术表达式错误！\n");

return ERROR; } } }

printf("算术表达式为：%s \n后缀表达式为：",Express);

while(SeQ.rear-SeQ.front!=0) //将队列输出即为表达式的后缀形式 { OutQueue(&SeQ,&c); printf("%c",c); } convert(Express);

printf("其结果为：%d\n",Pop(&OPND));

//输出表达式的值 return 0; }

实验结果：

4

本文来源：https://www.bwwdw.com/article/tt2i.html