精华内容
下载资源
问答
  • 中缀表达式
    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++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 题目:现有中缀表达式如:1+(2-3)*4+10/5 请用栈的特性编写一个程序,使得程序输出后缀表达式 分析如下: STEP1: 1+(2-3)...
  • 中缀表达式转换为后缀表达式(oj题库) 中缀表达式转换为后缀表达式(oj题库) 题目描述 中缀表达式是一个通用的算术或逻辑公式表示方法,操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的...
  • 本文实例为大家分享了C语言实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 中缀表达式转换为后缀表达式(思路) 1.创建栈 2.从左向右顺序获取中缀表达式 a.数字直接输出 b.运算符 情况一:遇到左...
  • 表达式2*(9+6/3-5)+4,称为中缀表达式,表示成2 9 6 3 / + 5 - * 4 +称为后缀表达式,表示成+ * 2 - + 9 / 6 3 5 4称为前缀表达式。 ·基本要求 将中缀表达式,转换为后缀表达式和前缀表达式,再分别计算转换后的...
  • 1) 实现一个完整的 Java 程序,它读取文件中的中缀表达式(每个表达式以分号结束,文件中可以有多个表达式)并转换为等价的后缀表达式后输出到屏幕上。表达式中的运算量可以是任意整数或者小数,支持加、减、乘、除...
  • 从键盘输入中缀表达式,建立操作数与运算符堆栈,计算并输出表达式的求值结果。 基本要求:实现 +, -, *, /四个二元运算符以及(); 操作数范围为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 上帝啊 家乡离我已有五百余里...
  • 自定义栈,中缀表达式转换为后缀表达式并求值,三个抽象数据类型定义(1.class stack 2.class Middle_expressionToPost_expression 3.class Post_expression_value)
  • 该程序实现了运算表达式转换为中缀表达式中缀表达式转换为后缀表达式及后缀表达式求值。该程序已实现加减乘除括号运算符及求余、幂指数的求解
  • 本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 一、思路:和中缀表达式的计算类似,只不过不用计算,把表达式输出即可 1.用字符数组存储整行输入的中缀表达式; 2.接着从...
  • 从键盘输入中缀表达式,建立操作数与运算符堆栈,计算并输出表达式的求值结果。 基本要求:实现 +, -, *, /四个二元运算符以及(); 操作数范围为0至9。 提高要求:实现+, -两个一元运算符(即正、负号); 操作...
  • c语言实现中缀表达式转后缀表达式并求得计算结果,用顺序栈结构。 当输入者输入错误信息的时候需要报错,并说明错误的种类。
  • 安装Parser Generator软件,熟悉其使用,对讲义中简单表达式计算的Yacc...3.修改Yacc程序,不进行表达式的计算,而是实现中缀表达式到后缀表达式的转换。 C语言版,包含.y和对应的两个.h,.c文件,在VS2013上编译成功。
  • (1) 从键盘或文件读入一个合法的算术表达式,输出相应的后缀表达式。后缀表达式中,数据与数据之间加分隔符; (2) 输出正确的计算结果,保留两位小数点; (3) 考虑算法的健壮性,当表达式错误时,要给出错误...
  • 数据结构C++版,将中缀表达式变换为后缀并用后缀表达式求值,支持运算符包括+,-,*,/,^,(),支持小数,负数,多位数运算
  • 先写词法分析的源文件,用正则表达式表示出需要识别的字符,例如数字,乘法,加法和括号,如果识别到其他非法字符需要报错,用flex生成lex.yy.c文件。语法分析用LR方法进行语法分析,LR方法需要先根据文法构造自动机...
  • c语言中缀表达式计算

    2015-01-03 18:15:23
    利用c语言写的中缀表达式,主要数据结构是栈。
  • 西南交通大学 报告仅供参考,请独立完成作业
  • 本资源是数据结构中利用顺序栈计算中缀表达式的一个C++代码,仅供参考,不足之处请大神们指正.
  • 能检查表达式合法性:括号匹配,小数点检查,空格处理,操作符检查 能求多位小数 整数
  • Python实现的编译原理中间代码生成程序,使用了PyQt5写图形界面 题目:设计一个程序,该程序能够将形如x=y op z的简单赋值语句翻译为对应的四元式序列,其中op可为+、-、*、/等二元运算符。要求用图形界面方式编程. ...
  • 08.中缀表达式转换后缀表达式算法.ppt
  • C++中缀表达式的计算

    2015-10-23 19:32:47
    利用c语言写的中缀表达式,主要数据结构是栈。
  • 中缀表达式转后缀表达式

    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++中缀表达式转后缀表达式的方法,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • python实现中缀表达式的计算,包括指数和对数。这个资源有利于初学者掌握中缀表达式

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,732
精华内容 10,292
关键字:

中缀表达式

友情链接: OpenVent_CPAP_pump_lid.zip