2022年逆波兰表达式求值 .pdf
题目: 逆波兰表达式求值学生姓名 : 李桐 20100820212 专业班级 : 通信工程二班背景表达式求值是程序设计语言编译中的一个最基本的问题因为任何程序设计语言都必须具有表达式求值的功能，同时表达式的计算应用也相当广泛，比如电力调度系统中的计算遥测、车站票务系统中的票价类型计算公式等。通常， 我们所说的表达式是由运算符、操作数、界限符所组成。而算术表达式中最常见的表示法形式有中缀、前缀和后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。1、中缀表达式将运算符放在两操作数的中间。在运算中存在运算符的优先权与结合性的问题。例如运算：a*b+(c-d/e)*f 时，编译器即自左向右逐一检查，当检查到第一个运算符“ * ”时还无法知道是否执行；待检查到第二个运算符“ + ”时，因为知道“*”的优先级别高于“ + ”时，才知道执行“a*b”；当继续检查到“ ( ”时，可知道先执行括号以内部分等。2、前缀表达式将运算符放在两操作数的前面。这种表示法经常用于计算机科学，特别是编译器设计方面。为纪念其发明家Jan Lukasiewicz，这种表示法也称波兰表示法。3、后缀表达式将运算符放在两操作数的后面。后缀表达式也称逆波兰表达式，因其使表达式求值变得轻松，所以被普遍使用。前缀和后缀表示法有三项公共特征：（ 1） 操作数的顺序与等价的中缀表达式中操作数的顺序一致（ 2） 不需要括号（ 3） 操作符的优先级不相关问题描述读入一个后缀表达式， 利用堆栈来计算该表达式的值，同时要效验后缀表达式是否正确。/*算法核心思想操作数入栈；遇到操作符时，操作数出栈，求值，将结果入栈；当一遍后，栈顶就是表达式的值。*/ #include #include #include using namespace std; typedef struct stack / 栈结构体 double num; stack *pre; stack; stack* top; / 定义全局变量栈顶名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - void initial(stack *& l) /初始化链表 l=(stack*)malloc(sizeof(stack); top=l; l-pre=NULL; bool pop(stack*& l , double &n)/出栈 if(top-pre=NULL) return false; n=top-num; top=top-pre; return true; void push(stack*& l , double n)/入栈 stack* temp; temp=(stack*)malloc(sizeof(stack); temp-num=n; temp-pre=top; top=temp; double caculater(double a , double b , char ch)/ 计算 switch(ch) case +:return a+b; case -:return a-b; case *:return a*b; case /:return a/b; default:printf(FALSE!n); double stringtodouble(char * input , int i) /将字符串转化为数字 double index=1; double sum=0; while(*(input+i)!=0) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - if(*(input+i)=.) /实现小数输入 i+; /跳过 .字符index=0.1; while(*(input+i)!=0) sum=sum+(*(input+i)-48)*index; index=index/10; i+; return sum; sum=sum*10+(*(input+i)-48); i+; return sum; int main() string in; char *input; stack* l; initial(l); while(cinin) input=(char *)malloc(in.length()+1)*(sizeof(char); /实现任意长度字符串输入in.copy(input,in.length(); inputin.length()=0; if(*input=-&(*(input+1)=0)&(*(input+1)=0)&(*(input)num); /打印结果getch(); return 0; /总结本实验的难点是对字符串的处理！ ！名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -
