用栈的方式实现表达式求值.doc

一、程序设计任务 掌握栈的用法，实现表达式求值这一栈的典型应用问题：以字符序列的形式从终端输入语法正确的、不含变量的算术表达式，利用算符优先关系，实现对算术四则混合运算表达式求值。当用户输入一个合法的表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号 。二、具体代码实现如下#include#include#include #include#include#include /cstdio本来就只是将stdio.h的内容用C+的头文件形式表现出来。 #define NULL 0 typedef struct node /定义一个结点结构体char date; struct node *next; SNode; SNode *InitStack()/初始化空链栈 SNode *top; top=new SNode;/top=(SNode *)malloc(sizeof(SNode); top-next=NULL; return top; void PushOptr(SNode *top,char x)/运算符进栈函数 SNode *p; p=new SNode; p-date=x; p-next=top-next; top-next=p; char PopOptr(SNode *top)/运算符出栈函数 SNode *p; char x; if(top=NULL) return NULL; p=top-next; x=p-date; top-next=p-next; delete p; return x; void PushOpnd(SNode *top,char x)/操作数进栈函数 SNode *p; p=new SNode; p-date=x; p-next=top-next; top-next=p; char PopOpnd(SNode *top)/操作数出栈函数 SNode *p; char x; if(top=NULL) return NULL; p=top-next; x=p-date; top-next=p-next; delete p; return x; char GetTop(SNode *top)/取栈顶元素 return (top-next)-date; int In(char c) int n; switch(c) case +: case -: case *: case /: case (: case ):case %:case :case #: n=1;break; default : n=0;break; return n; char Precede(char x,char y) /符号优先级规则说明 int i,j; int form99=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,1,-1,1,-1,-1,-1,-1,-1,0,-1,-1,2,1,1,1,1,2,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,2,-1,-1,0; /定义一个二维数组存放运算符优先级switch(x) case +:i=0;break; case -:i=1;break; case *:i=2;break; case /:i=3;break; case (:i=4;break; case ):i=5;break; case %:i=6;break;case :i=7;break;case #:i=8;break; switch(y) case +:j=0;break; case -:j=1;break; case *:j=2;break; case /:j=3;break; case (:j=4;break; case ):j=5;break; case %:j=6;break;case :j=7;break;case #:j=8;break; if(formij=1) /当formij=1时，说明运算符i的优先级高于运算符jreturn ; else if(formij=-1) /当formij=-1时，说明运算符i的优先级低于运算符jreturn ; else /当formij等于其他值时，说明运算符i的优先级等于运算符jreturn =; int Operate(char x,char z,char y)/操作函数 int a=x-0,b=y-0; switch(z) case +:return a+b; case -:return a-b; case *:return a*b; case /:return a/b; case %:return a%b; case : for(int i=1;ib;i+) a*=a; return a;/coutpow(a,b); char Eval_Exp(char t) /获取运算结果 char temp30; strcpy(temp,t); strcat(temp,#);char a,b,c,r,f,z; int result,i=0; SNode *top2; top0=InitStack(); /top0指向栈顶PushOptr(top0,#); /将#进入空运算符栈top1=InitStack(); c=tempi; while(c!=#|(GetTop(top0)!=#)/输入符号不为#或者栈顶元素不为#时执行while语句 if(!In(c) /如果当前输入不为运算符时执行if语句 PushOpnd(top1,c); /将输入的元素放入操作数栈中c=temp+i; else r=Precede(GetTop(top0),c); /获取符号优先级比较结果switch(r) case :b=PopOptr(top0); /出当前运算符栈中的栈顶元素a=PopOpnd(top1); /出当前操作数栈中栈顶元素 z=PopOpnd(top1); /出当前操作数栈中栈顶元素 result=Operate(z,b,a); /计算结果 f=result+0; PushOpnd(top1,f); /将运算结果进操作数栈中 break; return f; /返回运算结果 void main() char infilename40,outfilename40,ch30;fstream infile;fstream outfile;coutinfilename;infile.open(infilename,ios:in|ios:nocreate);if(!infile)cout不能打开文件：infilenameendl;exit(1);coutoutfilename;outfile.open(outfilename,ios:out);if(!outfile)cout