-
2020-04-23 00:36:27
优先函数实现表达式计算
左/右 + * ( ) i # + ·> <· <· ·> <· ·> * ·> ·> <· ·> <· ·> ( <· <· <· = <· ) ·> ·> ·> ·> i ·> ·> ·> ·> # <· <· <· <· 由优先表构造优先函数
优先函数 + * ( ) i # f 6 8 2 8 8 1 g 4 7 9 2 9 1 本程序使用C语言编写
支持整数加减乘除带括号的运算
核心部分和数据结构中利用栈实现表达式运算几乎相同
程序的难点在于优先级<、=、>分类讨论#include<stdio.h> #include<stdlib.h> #include <string.h> //优先函数 int fplus = 6; int gplus = 4; int fmul = 8; int gmul = 7; int fleft = 2; int gleft = 9; int fright = 8; int gright = 2; int fi = 8; int gi = 9; int fpound = 1; int gpound = 1; char expression[128]; int flag = 1; void Error() { printf("错误\n"); exit(0); } void Input() { //char over[] = {'#', '\0'}; printf("请输入表达式,以#结尾:"); gets(expression); //printf("Input: %s\n",expression); } int f(char opt) { if(opt == '+' || opt == '-') { return fplus; } else if (opt == '*' || opt == '/') { return fmul; } else if (opt == '(') { return fleft; } else if (opt == ')') { return fright; } else if (opt == 'i') { return fi; } else if (opt == '#') { return fpound; } return -1; } int g(char opt) { if(opt == '+' || opt == '-') { return gplus; } else if (opt == '*' || opt == '/') { return gmul; } else if (opt == '(') { return gleft; } else if (opt == ')') { return gright; } else if (opt == 'i') { return gi; } else if (opt == '#') { return gpound; } return -1; } int In(char num) { if(num == '0' ||num == '1' || num == '2' || num == '3' || num == '4' || num == '5'|| num == '6' || num == '7' || num == '8' || num == '9') return 1; else return -1; } int Operation(int a, char opt, int b) { switch(opt) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; default : return 0; } } int main() { int index_e = 0; // 字符串下标 int index_oprt = 0; // 算符栈下标 int index_opnd = 0; // 算量栈下标 int Sn[100]; char Sp[100]; int num1; int num2; char temp[100]; Sp[0] = '#'; Input(); //printf("算符栈: %s\n",Sp); while( flag == 1 ) { int t = 0; if( Sp[index_oprt] == '#' && expression[index_e] == '#' ) { //printf("都为#,结束\n"); flag = 0; } else if(Sp[index_oprt] == '(' && expression[index_e] == ')') { //printf("读到括号\n"); index_oprt--; index_e++; } else if(In(expression[index_e]) == 1) { //printf("读到数字\n"); while(In(expression[index_e]) == 1) { temp[t] = expression[index_e]; t++; index_e++; } //printf("temp: %s\n",temp); //atof()是把字符串转换成double Sn[index_opnd++] = atof(temp); //printf("number %d\n",Sn[index_opnd-1]); //清空temp for(int m=0; m<100; m++) temp[m] = '\0'; } else if(f(Sp[index_oprt]) < g(expression[index_e])) { //printf("%d %d\n",f(Sp[index_oprt]),g(expression[index_e])); //printf("小于\n"); Sp[index_oprt + 1] = expression[index_e]; index_oprt++; index_e++; //printf("%c 入栈\n",Sp[index_oprt]); } else if(f(Sp[index_oprt]) > g(expression[index_e])) { //printf("大于\n"); //出栈两个数 num2 = Sn[index_opnd - 1]; index_opnd--; num1 = Sn[index_opnd - 1]; index_opnd--; //算符栈出一个,算完了结果再入算量栈 Sn[index_opnd] = Operation(num1, Sp[index_oprt], num2); index_opnd++; index_oprt--; } else { Error(); } } printf("表达式的值为:%d\n", Sn[0]); return 0; }
运行截图:
更多相关内容 -
算符优先算法中优先函数的构造
2020-11-04 10:29:09算符优先分析中“优先函数的简单构造!”
这里我介绍的是一种简单的方法,不是书本的那个方法。是我后面那个参考资料上面的作者想出来的。因为这个是在知网上面找到的,是1997年的一篇文章。我就是一个总结,然后画几个比较清楚的图而已(因为从知网上下载的的pdf上面的图有点不太清楚)优先函数树形构造法
我们教材上面的就是陈火旺老师的那本,然后方法就是找节点。这个方法虽然简单,但是操作起来的却有些麻烦,因为我们作图的时候,难免就会看不清楚,或者数错。下面介绍的树形构造法就可以避免这个问题,仅仅只需要根据优先矩阵就可以得出正确结果。
操作步骤
对于一个优先表先做如下几个步骤(假设优先函数存在)
1 ) 对于f(a)对应行中“a>=b 的所有终结符b , 把g(b)作为f(a) 的子树。
2) 对g(a) 对应列中有b <=a 的. 把f(a) 作为g(b)的子树.
3 ) 对f(a)重做第( 1 ) 步, 对g(b) 重做第( 2 ) 步。
4) 重复出现的f或g , 作记号不再对其执行第( 1) , ( 2) 步
方向图
5) 构造f(a)函数时, 以f(a) 为根结点, 按( 1 ) ,(2 ),( 3),( 4) 执行.
6) 构造g(b)函数时, 以g(b) 为根结点, 按(2 ) ,( 1 ) , ( 3 ) , ( 4 ) 执行.
按照以上5步先画出树,然后查树的节点数(包括根节点,做记号的不查),即可以得到根节点的优先函数值。
但是我觉得这个操作步骤2有点问题。应该是b>=a的时候,就把f(a)作为g(b)的子树。我也自己做了实验,发现这样做才是正确的。不过也可能是我没有理解原作者的意思。反正,就目前看来,我都是按照如果b<=a,就把f(a)作为g(b)的子树。
所以,下面我举例的例子,第(2)步都是按照“b>=a的时候,就把f(a)作为g(b)的子树”这个来做的。举例操作
假如现有一个优先矩阵是这样的:这个例子是《编译原理》陈火旺老师(下面我说的教材,没有特别说明也是指的这本教材)那本书上面的。在90页。
那么我们现在用树形构造法来试试怎么得到这个优先函数。因为最后的答案是去掉了 i 和 # 之后得到的,所以我下面也将不会考虑 i 和 # 号。至于为什么不考虑 i 和 #,,就是因为这两个不是算符,我们算符优先函数主要针对的就是算符直接的优先级。但是优先关系矩阵中是给出了 i 和 # 与其他算符之间的优先关系的。我这里其实是有一个疑问的:因为在优先函数这里没有 i 的优先关系,那么在使用优先函数来分析一个句子是不是这个文法定义的合法的句子的时候,那么什么时候该移进这个 i 呢?希望知道的小伙伴可以在下面留言,我们讨论一下。计算f(+)的优先函数值。
- 从优先矩阵中可以得到:’+‘ >= 的算符有;’+’,’)’,’#'三个。因为不考虑i 和 #(下面就不提醒这一点了),所以f(+)的孩子节点有两个,分别是g(+)和g()),如下图所示。
- 现在就来找g(’+’) 的子树。我这里还是采用的是如果b>=a,就把f(a)作为g(b)的子树。从优先表中可以看到的就是’+‘ >= 的算符有:’(’。注意,我这里说的’+‘是g(’+‘),也就是从’+‘那一列中寻找。
所以,g(’+’)的子树就是f(’(’); - 然后找到g(’)’) >=的算符:
但是f(’(’)已经出现过了(作为g(’+’)子树出现的),所以就不用画出来了。 - 然后就是寻找f(’(’) >=的算符。
但是g(’)’)也已经出现过了,所以这里也不用画出来了。
- 最后每一个节点我们都已经检查过了,没有可以重新添加的了。也就是趋于稳定了(编译原理里面好多都是这样子的,得使所有都不再变化的时候,算法就算结束了)。我们数一下节点的个数,就是4个,和书本95页给出的答案是一样的。
同理,g(’+’)的树也可以这样画出来。我就给出最后的树,就不一一分析了。
自己的思考
本质上书本上的画图和这里的画一颗树,都是优先级高的指向优先级低的,所以入度为0的节点,给的优先函数值应大一点,出度为0的,给出的优先函数值应该小一点。
上面提到的这个简单的方法其本质善和我们教材上的方法是一样的。你可以将教材上的方法中的图给截取一部分出来。例如,你截取以g(’+’)作为顶点的树去看,发现就是和我上面画的一样。
还有注意的一点就是:我们求出一组优先函数之后,就可以构造出无数组优先函数。所以,如果你求出来的和参考答案给出的不是一样的,也不一定是你错了。只要你的优先函数之间的关系和参考答案上给出的关系是一样的就可以了。
参考资料
构造优先函数的更简单方法_树型构造_潘群娜
这个知网上我找到的一篇关于这个优先函数构造比较简单的方法,如果大家对上面的博客解释的不太清楚的话,可以去知网上看这个原作者写的文章。 - 从优先矩阵中可以得到:’+‘ >= 的算符有;’+’,’)’,’#'三个。因为不考虑i 和 #(下面就不提醒这一点了),所以f(+)的孩子节点有两个,分别是g(+)和g()),如下图所示。
-
优先函数c代码实现
2020-10-31 15:22:38编译原理之求算符优先函数的方法—迭代法 此博文包含图片 (2011-04-26 22:55:38)转载▼ 标签: 编译原理 算符优先函数 迭代法 教育 分类: IT乐园 编译原理之求算符优先函数的方法—迭代法 若已知运算符之间的优先...编译原理之求算符优先函数的方法—迭代法 此博文包含图片 (2011-04-26 22:55:38)转载▼ 标签: 编译原理 算符优先函数
迭代法 教育 分类: IT乐园 编译原理之求算符优先函数的方法—迭代法若已知运算符之间的优先关系,可按如下步骤构造优先函数:
1、对每个运算符a(包括#在内)令f(a)=g(a)=1
2、如果a⋗b且f(a)<=g(b)令f(a)=g(b)+1
3、如果a⋖b且f(a)>=g(b)令g(b)= f(a)+1
4、如果a≐b而f(a) ≠g(b),令min{f(a),g(b)}=max{f(a),g(b)}
5、重复2~4,直到过程收敛。如果重复过程中有一个值大于2n,则表明不存在算符优先函数。
程序实现代码为: #include <stdio.h> #include <stdlib.h> #define MaxSize 100 #define MaxOp 9 struct { char ch; //运算符 int pri; //优先级 } lpri[]={{'+',1},{'-',1},{'*',1},{'/',1},{'(',1},{')',1},{'#',1}}, rpri[]={{'+',1},{'-',1},{'*',1},{'/',1},{'(',1},{')',1},{'#',1}}; int f(char op) //求左运算符op的优先级 { int i; for (i=0;i<MaxOp;i++) if (lpri[i].ch==op) return lpri[i].pri; } int g(char op) //求右运算符op的优先级 { int i; for (i=0;i<MaxOp;i++) if (rpri[i].ch==op) return rpri[i].pri; } char Precede(char c1,char c2) { int i=0,j=0; static char array[49]={ '>', '>', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '<', '<', '<', '<', '<', '=', '!', '>', '>', '>', '>', '!', '>', '>', '<', '<', '<', '<', '<', '!', '='}; switch(c1) { 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; } switch(c2) { 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; } return (array[7*i+j]); } void main() { int i,j,k=1; while(k!=0) { k=0; for(i=0;i<7;i++) { for(j=0;j<7;j++) { if(Precede(lpri[i].ch,rpri[j].ch)=='>'&&f(lpri[i].ch)<=g(rpri[j].ch)) { lpri[i].pri=rpri[j].pri+1;k=1;} else if(Precede(lpri[i].ch,rpri[j].ch)=='<'&&f(lpri[i].ch)>=g(rpri[j].ch)) { rpri[j].pri=lpri[i].pri+1;k=1;} } } } printf(" "); for(i=0;i<7;i++) printf("<",lpri[i].ch); printf("\n"); printf("入栈优先函数f:"); for(i=0;i<7;i++) printf("=",lpri[i].pri); printf("\n"); printf("比较优先函数g:"); for(i=0;i<7;i++) printf("=",rpri[i].pri); printf("\n"); }
结果如下:
-
编译原理(五)自底向上优先分析法、简单优先分析、算符优先分析、最左素短语、优先函数
2020-06-21 15:05:30自底向上分析方法,也称...重复这一过程,直到栈中只剩文法的开始符号时,则分析成功,也就确认输入串是文法的句子。 5.1 自底向上优先分析法概述 5.2 简单优先分析法 5.3 算符优先分析法 ... -
编译原理实验——利用算符优先分析方法设计一个计算器
2020-09-23 09:47:33(Python实现,注释详细)直接输入:3+4*5,一般的...(1)第一阶段,运用算符优先分析算法完成计算器中对算术表达式的语法分析; (2)第二阶段,设计属性文法,改造第一阶段的程序,完成算术表达式的计算和相关的输出。 -
python基础编程:python 递归深度优先搜索与广度优先搜索算法模拟实现
2020-12-22 01:44:243、假设当前函数已经能用,调用自身计算上一次的结果,再求出本次的结果 (3)案例分析:求1+2+3+…+n的数和# 概述 ''' 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! ''' # 写... -
python 递归深度优先搜索与广度优先搜索算法模拟实现
2020-12-23 23:56:313、假设当前函数已经能用,调用自身计算上一次的结果,再求出本次的结果 (3)案例分析:求1+2+3+…+n的数和 # 概述 ''' 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! ''' # ... -
IDA 汇编命令分析以及函数调用过程
2017-08-15 19:39:41dll的文件,入口函数DllEntryPoint: .text:000000018000525C ; BOOL __stdcall DllEntryPoint(HINSTANCE hinstDLL, DWORD fdwReason, LPVOID lpReserved) .text:000000018000525C public DllEntryPoint .te -
函数实参计算顺序
2019-07-18 23:43:35根据这道题,我今天想记录两个知识点:一、逗号表达式(或者称逗号运算符),二、函数实参计算顺序 逗号表达式 最右边的(rec4,rec5)是逗号表达式,只能算作一个参数,其值为rec5。 关于逗号运... -
设计一个程序,演示用算符优先法对算术表达式求值的过程。利用算符优先关系,实现对算术四则混合运算表达式...
2021-11-15 12:13:24问题描述:设计一个程序,演示用算符优先法对算术表达式求值的过程。利用算符优先关系,实现对算术四则混合运算表达式的求值。 (1)输入的形式:表达式,例如2*(3+4)# 包含的运算符只能有’+’ 、’-’ 、’’ 、’... -
算符优先分析法-思路方法在这里
2020-05-16 20:48:284.任意输入一个输入串,可得到成功的分析或错误的提示,输出其分析过程或打印语法 分析树。 实验运行结果 算符优先文法的特点: 我们构造了算符优先语法分析器,就可以忽略原来的文法,栈中的非 -
PL/SQL存储函数,存储过程
2016-10-30 17:04:05存储过程和存储函数 存储过程和存储函数跟我们知道的表、视图、索引、序列、同义词等一样是我们数据中的对象。 笔记教程见:https://github.com/caojx-git/learn/blob/master/notes/oracle/PLSQL.sql 1.1什么是... -
函数式编程
2022-03-10 15:52:40函数式编程其实就是利用纯函数来实现一些细粒度的函数,然后再通过函数的组合把这些细粒度的函数组合成功能更强大的函数 -
优先队列 (结构体自定义比较)(重载函数)
2018-12-23 14:10:37之前一直在 用 sort 的结构体自定义函数,感觉到 STL 强大,今天刷题遇见优先队列 的题 ,要求跟 以前一样,数据量大,要求对某个信息排序,并且 做相应的 操作,如果用 普通的结构体来模拟 ,但是这个sort 要每次... -
循序渐进学Python之函数的嵌套
2021-01-14 01:18:11【51CTO独家特稿】我们...我们这里首先介绍了嵌套函数的定义,以及嵌套函数中变量的查找过程,然后后讲解多层嵌套函数的执行过程,最后说明了嵌套作用域的静态性。一、函数的嵌套定义学习过C语言的读者都知道,C语... -
Golang——秒懂函数、参数、可变参数、匿名函数、回调函数、内置函数
2022-01-25 10:05:08Golang——函数、参数、形参和实参、可变参数、返回值、函数重写、匿名函数、回调函数、内置函数 -
Excel-VBA基础语法(VBA简介、数据类型、变量、数组、运算符、内置函数、过程与函数)
2019-06-04 14:17:26)代码窗口:包含对象列表框、过程列表框、边界标识条、视图按钮、代码编辑区、过程分界线。 8 )立即窗口:一个重要用途是用来调试代码,想显示立即窗口,可以在视图选项卡中选择或者用快捷键 “Ctrl+G... -
python 函数详解
2021-03-17 00:59:59函数函数是代码的一种组织形式函数应该能完成一项特定的工作,而且一般一个函数只完成一项工作有些语言,分函数和过程两个概念,通俗解释是,有返回结果的是函数,无返回结果的叫过程,python不加以区分函数的使用... -
【编译原理】算符优先算法
2018-05-10 20:48:55G[E]:E→E+T∣T T→T*F∣FF→(E)∣i构造该算符优先文法的优先关系矩阵或优先函数;输入串应是词法分析的输出二元式序列,即某算术表达式“实验项目一”的输出结果。输出为输入串是否为该文法定义的算术表达式的判断... -
深度学习笔记:如何理解激活函数?(附常用激活函数)
2021-04-13 22:06:54文章目录@[toc]一、什么是激活函数?二、常见的激活函数1. Sigmoid函数2. Tanh/双曲正切激活函数3. ReLU激活函数4. Leaky ReLU5. Parametric ReLU激活函数6. ELU激活函数7. SeLU激活函数8. Softmax激活函数9. Swish... -
常用激活函数(激励函数)理解与总结
2018-05-13 23:07:19学习神经网络的时候我们总是听到激活函数这个词,而且很多资料都会提到常用的激活函数,比如Sigmoid函数、tanh函数、Relu函数。那么我们就来详细了解下激活函数方方面面的知识。本文的内容包括几个部分: 什么是... -
算符优先分析算法及其代码实现
2020-11-06 23:01:52做算术式的四则运算时,为了保证计算 结果和过程的唯一性,规定了一个统一的四则运算法则, 确定运算符之间的优先关系。 2. 算符优先分析的步骤 构造优先关系矩阵(通过FIRSTVT和LASTVT集构造) 构造一个输入串(要... -
【C++】C++运算符重载(成员函数实现、友元函数实现)
2018-06-10 20:29:03运算符重载 对于面向对象的程序设计来说,运算符重载可以完成两个对象之间的复杂操作...为了重载运算符,首先要定义运算符重载函数,它通常是类的非静态成员函数或者友元函数,运算符的操作数通常也应为对象。 定... -
C/C++计算器(利用栈表达式求值,支持函数运算)
2017-12-13 16:22:06其实现思想和数据结构书上基本一致,不同的增加的函数计算,并可以扩充,利用两个栈:一个操作数栈和一个运算符栈。计算器C/C++实现代码: (开发环境:Dev-Cpp编译器)1.Express.h 代码:#include #include #... -
函数:递归是神马&课后作业,小,甲鱼,Python
2020-12-06 13:43:25笔记递归(recursion)片面来说:函数不断调用自身,并且最终达到某个条件而停止,这是...递归与迭代的区别递归(recursion):递归常被用来描述以自相似方法重复事物的过程,在数学和计算机科学中,指的是在函数定义中... -
4. 构造【算符优先分析表】步骤 + 判断是否为【算符优先文法】
2022-04-28 15:18:49算符优先分析法就是仿照算术表达式的四则运算过程而设计的一种语法分析方法。 这种分析方法首先要规定运算符之间(确切地说终结符之间)的优先关系和结合性质,然后借助这种关系,比较相邻运算符的优先级来确定句型... -
python函数
2020-12-05 21:12:06函数定义: 函数是指将一组语句的集合通过一个名字(函数名)封装起来,要想执行这个函数,只需调用其函数名即可函数特性:def my_sum(x,y): #定义函数名res = x+yreturn res #返回函数执行结果c = my_sum(4,5) #结果... -
CPP函数
2020-05-16 07:21:02文章目录 函数 内联(inline)函数 函数模板 具有默认参数值的函数 作用域(scope) 存储类别(storage duration) 变量 全局变量 局部变量 函数 内联(inline)函数 在c++中inline关键字可以用来修饰函数,用来在编译阶段... -
matlab 饱和函数 sat
2021-05-05 10:19:46二维图形 同时绘制多个函数图像 ? plot(x1,y1,s1,x2,y2,s2, ... ,xn,yn,sn) 等价于: hold on plot(x1,y1,s1) plot(x2,y2,s2) ... plot(xn,yn,sn) 属性选项 可以省略 对数坐标图形 MATLAB提供了绘制对数和半对数........ -
【20200423】编译原理课程课业打卡十八之构造文法算符优先关系表&求解输入串算符归约过程
2020-04-29 19:41:103、如何计算算符优先关系 4、算符优先分析算法 5、关于句型的短语&素短语 6、算符优先文法(OPG)条件 7、规范规约&算符优先规约 实例对比 叮嘟!这里是小啊呜的学习课程资料整理。好记性不如烂笔头,今天也是努力...