-
2021-11-13 10:49:29
目录
中缀表达式求值
算法思想:把数字和操作符分别放在栈中,遇到操作符时,与栈顶操作符的优先级比较,如果优先级比栈顶的低就进行运算。
#include<stack> #include<stdlib.h> #include<iostream> #include<ctype.h> #include<string.h> using namespace std; int pre(char c)//优先级判断 { if(c=='=') return 0; else if(c=='+'||c=='-') return 1; else if(c=='*'||c=='/') return 2; else return 0; } void calculate(stack<double> &num,stack<char> &op)//运算 { double b=num.top(); num.pop(); double a=num.top(); num.pop(); switch(op.top()) { case '+': num.push(a+b); break; case '-': num.push(a-b); break; case '*': num.push(a*b); break; case '/': if(b==0)throw"错误:除数为0"; else { num.push(a/b); break; } } op.pop(); } int main() { try { stack<double> num;//存储数字 stack<char> op;//存储操作符 string s; cin>>s;//读取整个字符串 for(int i=0; s[i]!='\0'; i++) { if(isdigit(s[i]))//判断是否为数字 { double temp=atof(&s[i]);//转化为浮点数 num.push(temp);//入栈 while(isdigit(s[i])||s[i]=='.')//寻找下一个操作符 i++; i--;//由于有外层循环,往前挪一位 } else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='('||s[i]==')'||s[i]=='=')//字符是操作符 { if(s[i]=='(') op.push(s[i]); else if(s[i]==')') { while(op.top()!='(')//计算括号内的式子 calculate(num,op); op.pop();//左括号出栈 } else if(op.empty()||pre(s[i])>pre(op.top()))//优先级大于栈顶,或栈为空时,直接进栈 op.push(s[i]); else if(!op.empty()&&pre(s[i])<=pre(op.top()))//是优先级不大于栈顶的操作符,且栈不空,先进行运算操作 { while(!op.empty()&&pre(s[i])<=pre(op.top())) calculate(num,op); op.push(s[i]);//将优先级大于它的操作做完再让它进栈 } } else throw"错误:输入不符合规范"; } printf("%.2lf\n",num.top());//输出结果 num.pop(); op.pop();//清空栈 } catch(const char *mess) { cout<<mess<<endl ; } return 0; }
输入: 0.6*(10.6-1.9/2)+5.6=
输出:11.39中缀表达式转化为二叉树
采用中缀表达式求值的算法思想,只是操作数栈中用存储指向结点的指针来代替存储操作数。采用中缀表达式求值的算法思想,只是操作数栈中用存储指向结点的指针来代替存储操作数。
此处为了方便操作,用字母代替数字,并默认表达式无错误
#include<stack> #include<stdlib.h> #include<iostream> #include<string.h> using namespace std; class treenode { public: treenode *left; treenode *right; string data; }; class tree { public: treenode *root; //根节点 tree(treenode *x); //以一个节点为根节点构造书 ~tree() {}; //析构函数 void print(); //输出树 void preorder(const treenode *treeroot); //先序遍历 void inorder(const treenode *treeroot); //中序遍历 }; tree::tree(treenode *x) { root=x; } void tree::preorder(const treenode *treeroot) //先序遍历 { if(treeroot!=NULL&&!treeroot->data.empty()) { cout<<treeroot->data<<' '; preorder(treeroot->left); preorder(treeroot->right); } } void tree::inorder(const treenode *treeroot) //中序遍历 { if(treeroot!=NULL) { inorder(treeroot->left); cout<<treeroot->data<<' '; inorder(treeroot->right); } } void tree::print() //输出树 { cout<<"先序:"; preorder(root); cout<<endl<<"中序:"; inorder(root); } int pre(char c)//优先级判断 { if(c=='=') return 0; else if(c=='+'||c=='-') return 1; else if(c=='*'||c=='/') return 2; else return 0; } void calculate(stack<treenode*> &num,stack<char> &op)//运算 { treenode * b=new treenode; //创建新节点,且储存字母1 b = num.top(); num.pop(); treenode * a=new treenode; //创建新节点,且储存字母2 a=num.top(); num.pop(); treenode *cur=new treenode; //创建新节点,且储存操作符 cur->left=a; cur->right=b; cur->data=op.top(); num.push(cur); //新的子树压入栈中 op.pop(); } int main() { stack<treenode*> num;//存储节点 stack<char> op;//存储操作符 char s; while((s=getchar())!='\n') { if(s>='a'&&s<='z')//判断是否为字母 { treenode *p=new treenode; p->data=s; p->left=NULL; p->right=NULL; num.push(p);//入栈 } else if(s=='+'||s=='-'||s=='*'||s=='/'||s=='('||s==')'||s=='=')//字符是操作符 { if(s=='(') op.push(s); else if(s==')') { while(op.top()!='(')//计算括号内的式子,生成新的子树 calculate(num,op); op.pop();//左括号出栈 } else if(op.empty()||pre(s)>pre(op.top()))//优先级大于栈顶,或栈为空时,直接进栈 op.push(s); else if(!op.empty()&&pre(s)<=pre(op.top()))//是优先级不大于栈顶的操作符,且栈不空,先进行运算操作,生成新的子树 { while(!op.empty()&&pre(s)<=pre(op.top())) calculate(num,op); op.push(s);//将优先级大于它的操作做完再让它进栈 } } } tree x(num.top()); //以当前节点为根节点产生二叉树 x.print(); //显示二叉树 op.pop();//清空栈 return 0; }
输入:a*(b+c)-d/e=
输出:先序:- * a + b c / d e
中序:a * b + c - d / e更多相关内容 -
C++利用栈实现中缀表达式转后缀表达式
2020-12-20 20:40:51本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 题目:现有中缀表达式如:1+(2-3)*4+10/5 请用栈的特性编写一个程序,使得程序输出后缀表达式 分析如下: STEP1: 1+(2-3)... -
中缀表达式转换为后缀表达式(oj题库)
2020-12-21 14:20:18中缀表达式转换为后缀表达式(oj题库) 中缀表达式转换为后缀表达式(oj题库) 题目描述 中缀表达式是一个通用的算术或逻辑公式表示方法,操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的... -
C语言实现中缀表达式转换为后缀表达式
2020-12-20 17:10:56本文实例为大家分享了C语言实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 中缀表达式转换为后缀表达式(思路) 1.创建栈 2.从左向右顺序获取中缀表达式 a.数字直接输出 b.运算符 情况一:遇到左... -
中缀表达式输入、转换与计算(前缀和后缀)内附流程图
2018-11-17 11:25:35表达式2*(9+6/3-5)+4,称为中缀表达式,表示成2 9 6 3 / + 5 - * 4 +称为后缀表达式,表示成+ * 2 - + 9 / 6 3 5 4称为前缀表达式。 ·基本要求 将中缀表达式,转换为后缀表达式和前缀表达式,再分别计算转换后的... -
检查中缀表达式并报错
2019-01-09 12:14:111) 实现一个完整的 Java 程序,它读取文件中的中缀表达式(每个表达式以分号结束,文件中可以有多个表达式)并转换为等价的后缀表达式后输出到屏幕上。表达式中的运算量可以是任意整数或者小数,支持加、减、乘、除... -
数据结构实验报告-栈与队列-中缀表达式求值-实验内容及要求.docx
2021-05-03 07:06:17从键盘输入中缀表达式,建立操作数与运算符堆栈,计算并输出表达式的求值结果。 基本要求:实现 +, -, *, /四个二元运算符以及(); 操作数范围为0至9。 提高要求:实现+, -, *, /四个二元运算符以及(); 实现+... -
中缀表达式
2018-10-08 23:49:39中缀表达式 直接计算结果。Away from home, away from home, 背负一切 离乡背井 away from home, away from home, 家在远方 我却再难回去 Lord, I'm five hundred miles away from home 上帝啊 家乡离我已有五百余里... -
自定义栈中缀表达式转换为后缀表达式并求值
2018-05-20 19:21:42自定义栈,中缀表达式转换为后缀表达式并求值,三个抽象数据类型定义(1.class stack 2.class Middle_expressionToPost_expression 3.class Post_expression_value) -
中缀表达式转换为后缀表达式及逆波兰式求值
2020-01-10 11:38:17该程序实现了运算表达式转换为中缀表达式、中缀表达式转换为后缀表达式及后缀表达式求值。该程序已实现加减乘除括号运算符及求余、幂指数的求解 -
C++实现中缀表达式转后缀表达式
2020-12-20 20:12:44本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 一、思路:和中缀表达式的计算类似,只不过不用计算,把表达式输出即可 1.用字符数组存储整行输入的中缀表达式; 2.接着从... -
数据结构实验报告3-栈与队列-中缀表达式求值-实验内容及要求.docx
2019-07-06 20:44:43从键盘输入中缀表达式,建立操作数与运算符堆栈,计算并输出表达式的求值结果。 基本要求:实现 +, -, *, /四个二元运算符以及(); 操作数范围为0至9。 提高要求:实现+, -两个一元运算符(即正、负号); 操作... -
c语言实现中缀表达式转后缀并求值
2018-04-09 17:08:23c语言实现中缀表达式转后缀表达式并求得计算结果,用顺序栈结构。 当输入者输入错误信息的时候需要报错,并说明错误的种类。 -
YACC 中缀表达式到后缀表达式
2016-11-24 21:58:11安装Parser Generator软件,熟悉其使用,对讲义中简单表达式计算的Yacc...3.修改Yacc程序,不进行表达式的计算,而是实现中缀表达式到后缀表达式的转换。 C语言版,包含.y和对应的两个.h,.c文件,在VS2013上编译成功。 -
后缀表达式相关,包括中缀表达式转后缀表达式以及后缀表达式的运算
2020-01-10 16:49:32(1) 从键盘或文件读入一个合法的算术表达式,输出相应的后缀表达式。后缀表达式中,数据与数据之间加分隔符; (2) 输出正确的计算结果,保留两位小数点; (3) 考虑算法的健壮性,当表达式错误时,要给出错误... -
中缀表达式变换为后缀并用后缀表达式求值
2019-04-27 14:41:27数据结构C++版,将中缀表达式变换为后缀并用后缀表达式求值,支持运算符包括+,-,*,/,^,(),支持小数,负数,多位数运算 -
编译原理——中缀表达式转后缀表达式
2018-12-18 09:06:23先写词法分析的源文件,用正则表达式表示出需要识别的字符,例如数字,乘法,加法和括号,如果识别到其他非法字符需要报错,用flex生成lex.yy.c文件。语法分析用LR方法进行语法分析,LR方法需要先根据文法构造自动机... -
c语言中缀表达式计算
2015-01-03 18:15:23利用c语言写的中缀表达式,主要数据结构是栈。 -
数据结构实验报告-栈与队列-中缀表达式转换为后缀式5分-实验内容及要求.docx
2021-03-11 14:50:56西南交通大学 报告仅供参考,请独立完成作业 -
利用顺序栈实现中缀表达式的计算问题
2015-11-17 14:02:57本资源是数据结构中利用顺序栈计算中缀表达式的一个C++代码,仅供参考,不足之处请大神们指正. -
中缀表达式求值(C++ 含合法性检查,多位数,浮点数)
2019-03-01 19:40:11能检查表达式合法性:括号匹配,小数点检查,空格处理,操作符检查 能求多位小数 整数 -
中间代码生成代码(中缀表达式转换为四元式)
2018-05-31 21:32:15Python实现的编译原理中间代码生成程序,使用了PyQt5写图形界面 题目:设计一个程序,该程序能够将形如x=y op z的简单赋值语句翻译为对应的四元式序列,其中op可为+、-、*、/等二元运算符。要求用图形界面方式编程. ... -
08.中缀表达式转换后缀表达式算法.ppt
2021-03-02 18:10:5408.中缀表达式转换后缀表达式算法.ppt -
C++中缀表达式的计算
2015-10-23 19:32:47利用c语言写的中缀表达式,主要数据结构是栈。 -
中缀表达式转后缀表达式
2022-07-06 09:37:09中缀表达式转后缀表达式中缀表达式转后缀表达式
1 后缀式简介
一种不需要括号的后缀表达法,也把它称为 逆波兰表示,是波兰逻辑学家卢卡西维奇(Lukasiewicz)发明的一种表示表达式的方法。
2 由中缀表达式求后缀表达式示例(3种方法)
中缀表达式指的是“9+(3-1)×3+8÷2”,这种就是我们通常见到的书写算式顺序,要计算中缀表达式则首先要将字符串转换为后缀表达式,即
9 3 1 - 3 * + 8 2 / +
,以下均是对于“9+(3-1)×3+8÷2”算式求解后缀表达式的方法。2.1 方法一:栈的应用-四则运算表达式求值
2.1.1 栈的应用-四则运算表达式求值规则
1.设定运算符栈;
2.从左到右遍历中缀表达式的每个数字和运算符;
3.若当前字符是数字,则直接输出成为后缀表达式的一部分;
4.若当前字符为运算符,则判断其与栈顶运算符的优先级,若优先级大于栈顶运算符,则进栈;若优先级小于栈顶运算符,退出栈顶运算符成为后缀表达式的一部分,然后将当前运算符放入栈中;
5.若当前字符为“(”,进栈;
6.若当前字符为“)”,则从栈顶起,依次将栈中运算符出栈成为后缀表达式的一部分,直到碰到“(”。将栈中“(”出栈,不需要成为后缀表达式的一部分,然后继续扫描表达式直到最终输出后缀表达式为止。2.1.2 栈的应用-四则运算表达式求值示例
1、初始化一个空栈。此栈用来对运算符进出栈使用。如图2-1-2-1的左图所示。
2、第一个字符是数字9,直接输出9(根据规则3),第二个字符是运算符“+”,则“+”进栈(根据规则4),如图2-1-2-1的右图所示。
图2-1-2-1 3、第三个字符是符号“(”,则“(”进栈(根据规则5),如图2-1-2-2左图所示。4、第四个字符是数字3,直接输出3(根据规则3),总输出表达式为
9 3
第五个字符是运算符“-”,则“-”进栈(根据规则4),第六个字符是数字1,直接输出1(根据规则3),总输出表达式为
9 3 1
如图2-1-2-2右图所示。
图2-1-2-2 5、第七个字符是符号“)”,此时依次将栈中运算符出栈成为后缀表达式的一部分,直到碰到"(",此时“(”上方只有“-”运算符,因此输出“-”运算符(根据规则6),总输出表达式为9 3 1 -
如图2-1-2-3左图所示。
6、第八个字符是数字3,直接输出3(根据规则3),总输出表达式为
9 3 1 - 3
第九个字符是运算符“”,因为此时的栈顶符号是运算符“+”,优先级低于“”,因此不输出,“*”进栈(根据规则4),如图2-1-2-3右图所示。
图2-1-2-3 7、第十个符号是运算符“+”,此时栈顶符号是“*”,比“+”运算符的优先级高。因此栈中元素出栈并成为后缀表达式的一部分(没有比“+”运算符更低的优先级,所以全部出栈),总输出表达式为9 3 1 - 3 * +
后把第十个符号“+”进栈(根据规则4)。
之前输出成为后缀表达式的“+”是中缀表达式中“9 + ”的“+”,现在入栈的“+”是中缀表达式中“9 + (3 - 1) × 3 +”的“+”。如图2-1-2-4左图所示。8、第十一个符号是数字8,直接输出8(根据规则3),总输出表达式为
9 3 1 - 3 * + 8
第十二个符号是运算符“÷”,则“/”进栈(根据规则4),如图2-1-2-4右图所示。
图2-1-2-4 9、第十三个字符也就是最后一个字符是数字2,直接输出2(根据规则3),总输出表达式为9 3 1 - 3 * + 8 2
如图2-1-2-5左图所示。
10、因为已经到了最后一个字符,所以将栈中符号全部出栈成为后缀表达式的一部分,最终输出表达式为
9 3 1 - 3 * + 8 2 / +
如图2-1-2-5右图所示。
图2-1-2-5 整个过程,都充分利用了栈的后进先出特性来处理。------以上过程参考《大话数据结构》中“栈的应用-四则运算表达式求值”内容。
2.2 方法二:二叉树应用
2.2.1 二叉树应用规则
后序遍历(LRD)是二叉树遍历的一种,也叫做后根遍历、后序周游,可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中,先左后右再根,即首先遍历左子树,然后遍历右子树,最后访问根结点。
------粘百度百科2.2.2 二叉树应用示例
直接根据表达式转换画二叉树(画二叉树过程不在描述),如图2-2-2-1所示,之后进行后序遍历便可得到后缀表达式。
图2-2-2-1 最后输出后缀表达式为:9 3 1 - 3 * + 8 2 / +
2.3 方法三:加括号法
2.3.1 加括号法规则
1、根据运算符的优先级对中缀表达式加括号(有几个运算符就有几对括号,原有的括号不用加)
2、将运算符移到对应括号后面
3、去掉所有括号,即为后缀表达式
------粘百度百科2.3.2 加括号法示例
中缀表达式为“9+(3-1)×3+8÷2”
1、变为((9+((3-1)×3))+(8÷2)) 2、变为((9((31)-3)*)+(82)/)+ 3、得到9 3 1 - 3 * + 8 2 / +
最后输出后缀表达式为
9 3 1 - 3 * + 8 2 / +
-
C++中缀表达式转后缀表达式的方法
2020-08-19 06:40:18主要介绍了C++中缀表达式转后缀表达式的方法,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下 -
python实现中缀表达式的计算,包括指数和对数
2018-10-13 09:39:31python实现中缀表达式的计算,包括指数和对数。这个资源有利于初学者掌握中缀表达式。