精华内容
下载资源
问答
  • 本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 题目:现有中缀表达式如:1+(2-3)*4+10/5 请用栈的特性编写一个程序,使得程序输出后缀表达式 分析如下: STEP1: 1+(2-3)...
  • C#使用栈实现中缀转后缀表达式并计算结果。
  • 本文实例为大家分享了C语言实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 中缀表达式转换为后缀表达式(思路) 1.创建栈 2.从左向右顺序获取中缀表达式 a.数字直接输出 b.运算符 情况一:遇到左...
  • 中缀转后缀表达式计算实现源码(C++、Java)
  • 编译原理实验一中缀表达式转后缀表达式
  • NULL 博文链接:https://128kj.iteye.com/blog/1623312
  • 用dev c++写的代码,附有啰里啰嗦的注释和测试样例。太简单了不好意思要分。
  • 中缀表达式转换为后缀表达式(oj题库) 中缀表达式转换为后缀表达式(oj题库) 题目描述 中缀表达式是一个通用的算术或逻辑公式表示方法,操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的...
  • 已知一个中缀表达式,将其转化为后缀表达式的代码实现。
  • 一、中缀转后缀 1、从左往右扫描中缀表达式,如果是数字,写入结果表达式,如果是操作数,需要进一步判断 2、(1)如果是左括号’(’,直接入栈 (2)如果是运算符,(‘+’、‘-’、‘*’、‘/’),先判断栈顶的...

    一、中缀转后缀
    1、从左往右扫描中缀表达式,如果是数字,写入结果表达式,如果是操作数,需要进一步判断
    2、(1)如果是左括号’(’,直接入栈
    (2)如果是运算符,(‘+’、‘-’、‘*’、‘/’),先判断栈顶的操作数的优先级,如果是左括号直接入栈,若如果是运算符,运算符优先级小于或等于栈顶运算符,将栈顶的运算符出栈,并将该运算符入栈
    (3)如果是右括号,将栈中运算符依次出栈,括号不用写入结果表达式
    (4)表达式扫描完了后,将栈中操作数依次出栈,并写入结果表达式就可以了。

    下面是天勤数据结构视频中的一道例题:
    在这里插入图片描述
    二、中缀转前缀
    步骤与前面基本一致,不过是从后往前扫描,中缀转前缀:当前读取运算符优先级小于栈顶则出栈;中缀转前缀:当前读取运算符优先级小于或等于栈顶运算符优先级则出栈

    附图:
    在这里插入图片描述

    展开全文
  • (1) 从键盘或文件读入一个合法的算术表达式,输出相应的后缀表达式后缀表达式中,数据与数据之间加分隔符; (2) 输出正确的计算结果,保留两位小数点; (3) 考虑算法的健壮性,当表达式错误时,要给出错误...
  • 前缀表达式:不含括号的算术表达式,而且是将运算符写在前面,操作数写在后面的表达式。求法:首先从右往左扫描表达式,从右边第一个字符判断,如果当前字符是数字,则一直到字符串的末尾再记录下来;如果是运算符,...

    前缀表达式:

    不含括号的算术表达式,而且是将运算符写在前面,操作数写在后面的表达式。

    求法:

    首先从右往左扫描表达式,从右边第一个字符判断,如果当前字符是数字,则一直到字符串的末尾再记录下来;如果是运算符,则将右边最近的两个数字串做相应的运算,以此作为一个新串并记录下来。一直扫描到最左端停止。

    例子:(a + b)* (c + d) :  *+ab+cd。理解:根据优先级,把数字位置不同,有那两个可以做运算,将运算符写在对应的数字前面,做完数字之后还有的元素,放在最前面。

    中缀表达式:

    是一个通用的算术或逻辑公式表达方法,操作符是以中缀形式处于操作数中间,即我们常用的算术表达方式。

    注意:中缀记法中括号是必须的。计算过程中用括号将相应的操作数和运算符括起来,用于指示运算的次序。

    后缀表达式:

    不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。

    例子:(2 + 3)* 4 : 23+4*。理解:和前缀区别不大,是从左往右,保证数字字符的顺序位置不变即可。

    分析过程:


    参考代码:

    #include<iostream>
    #include<stack>
    #include<string.h>
    #include<ctype.h>//用于类型判断 
    using namespace std;
    stack<char> op; // 操作符栈 
    
    char ans[1000];
    int priority(char ch){
    	switch(ch){
    		case '(' : return -1;
    		case '+':
    	    case '-': return 1;
    	    case '/':
    	    case '*': return 2;
    	}
    }
    
    bool isOperator(char ch){
    	if(ch == '+' || ch == '-' || ch == '/' || ch == '*'){
    		return true;
    	}
    	return false;
    }
    
    bool isCharacter(char ch){
    	if(ch >= '0' && ch <= '9' || ch >= 'a' && ch <= 'z' 
    	    || ch >= 'A' && ch <= 'Z'){
    	    	return true;
    		}
    	    return false;
    }
    
    int main(){
    	
    	string str;
    	while(cin >> str){
    		int k = 0;
    		int len = str.length();
    		str[len] = '#';
    		for(int i = 0; i <= len; i ++){// isdigit(str[i]) || isalpha(str[i])
    			if(isCharacter(str[i])){
    				ans[k ++] = str[i];
    			}
    			else if(isOperator(str[i])){
    //				ans[k ++] = '#';
    				if(op.empty()){
    					op.push(str[i]);
    				}
    				else{
    					while(!op.empty() && priority(op.top()) >= priority(str[i])){
    						ans[k ++] = op.top();
    						op.pop();
    					}
    					op.push(str[i]);
    				}
    			}
    			else if(str[i] == '('){
    				op.push(str[i]);
    			}
    			else if(str[i] == ')'){
    				while(op.top() != '('){
    					ans[k ++] = op.top();
    					op.pop();
    				}
    				op.pop();
    			}
    			else if(str[i] == '#'){
    				while(!op.empty()){
    					ans[k ++] = op.top();
    				    op.pop();
    				}	
    			}
    		}
    		cout << ans << endl;
    	} 
    	return 0;
    } 
    测试截图:



    以上就是这篇的内容,欢迎指出错误和不足之处,谢谢!

    展开全文
  • 主要为大家详细介绍了C++实现中缀表达式转后缀表达式,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 中缀表达式转后缀表达式求值

    千次阅读 2019-03-27 17:29:59
    刚开始想一鼓作气把整个过程全部实现,但白费了那几个小时,调试了半天也没做出来,后来我是通过先实现中缀表达式转化为后缀表达式,然后实现后缀表达式的求值,然后将两块代码进行合成,刚才同学还笑着说:模块化...

    刚开始想一鼓作气把整个过程全部实现,但白费了那几个小时,调试了半天也没做出来,后来我是通过先实现中缀表达式转化为后缀表达式,然后实现后缀表达式的求值,然后将两块代码进行合成,刚才同学还笑着说:模块化编程。。。

     

    直接在代码中解释。

    中缀表达式转后缀表达式:

    # include <iostream>
    # include <string>
    # include <sstream>
    # include <cctype>                //程序中需使用isdigit()函数,目的在于判别字符是否为数字,将符号和数字区别开来
    using namespace std;
    struct sign                      //建立存储符号的结构体
    {
    	char sign;
    	int level;
    	struct sign *next_1;
    };
    class linkstack
    {
    private:
    	struct sign *top;
    public:
    	linkstack() { top = NULL; }   //无参构造函数,top头指针初始化为零
    	char push_out();              //将栈顶元素出栈
    	void push_in(char new_sign);  //给栈中添加新元素
    	char print_top();             //返回栈顶元素中的符号内容
    	int print_level();            //返回栈顶元素符号的优先级
    };
    int compare(char compared_sign)   //给每个符号赋予优先级
    {
    	int level;
    	switch (compared_sign) {
    	case '(':
    		level = -10; break;
    	case ')':
    		level = -10; break;
    	case '+':
    		level = 0; break;
    	case '-':
    		level = 0; break;
    	case '*':
    		level = 1; break;
    	default:                     //default要加上
    		level = 1; break;
    	}
    	return level;
    }
    char linkstack::print_top()
    {
    	char result;
    	result = top->sign;
    	return result;
    }
    int linkstack ::print_level()
    {
    	return top->level;
    }
    char linkstack::push_out()               //删除栈顶元素
    {
    	char char_result;
    	struct sign *p;
    	char_result = top->sign;
    	p = top;
    	top = top->next_1;
    	delete p;
    	return char_result;                  //删除后需要给sting对象b中追加,所以需要返回
    }
    void linkstack::push_in(char new_sign)
    {
    	struct sign *s;
    	s = new struct sign;                 //添加栈顶元素
    	s->sign = new_sign;
    	s->level = compare(new_sign);
    	s->next_1 = top;
    	top = s;
    }
    int main()
    {
    	int count = 0; double m;           //count用来记录符号栈中的个数,用top!=NULL也可以
    	string a,b;
    	cin >> a;                          //string对象a是转化前的,b是转换后的
    	linkstack one;
    	for (auto c = a.begin(); c != a.end(); c++) {          //从a的第一个元素开始扫描
    		if (isdigit(*c)) {
    			b.push_back(*c);  continue;            //如果是数字isdigit(*c)为真,就给b中追加,进行下一个循环
    		}
    		else {
    			if (*c != ')'&&count==0) {            //如果栈为空,直接加入栈顶元素
    				one.push_in(*c);
    				count++;                         //记录栈元素的个数
    				continue;                        //进行下一个循环
    			}
    			if (*c==')') {                      //进行括号中的运算
    				while (one.print_top()!= '(') {             //一直循环到栈顶元素不等于‘(’
    					b.push_back(one.print_top());           //将目前栈顶元素追加给b
    					one.push_out(); count--;                //追加完后,删除栈顶元素,个数减一
    				}
    				one.push_out(); count--;                   //最后记得还要把左括号删除,以避免对下一个运算影响
    				continue;
    			}
    			if (compare(*c) <= one.print_level()) {     //如果当前符号优先级小于栈顶元素的优先级(即上一个运算符)
    				b.push_back(one.print_top());           //将栈顶运算符元素追加给b
    				one.push_out();                         //紧跟着删除刚才的栈顶元素
    				one.push_in(*c);                        //将当前的运算符号压入栈
    				continue;                               //进行下一个循环
    			}
    			if (compare(*c)>one.print_level()) {        //如果当前运算符优先级大于栈顶元素(即前一个运算符)
    				one.push_in(*c); count++;               //直接压入栈,个数加一,并进行下一个循环
    				continue;
    			}
    		}
    	}
    	if (count) {                                        //如果栈不空则还剩余一个符号没有追加给b
    		b.push_back(one.print_top());                   //追加栈中剩余的符号
    		one.push_out();
    	}
    	cout << b << endl;
    	system("pause");
    	return 0;
    }
    

    后缀表达式求值:

    # include <iostream>
    # include <string>
    # include <sstream>                    //下边程序中从string类型到double中要用到,具体的用法在以前的博客中我有详细提及
    using namespace std;
    struct operate         
    {
    	double member;         
    	struct operate *next;
    };
    class new_linkstack
    {
    public:
    	new_linkstack() { top = NULL; }      //初始化,top为NULL;
    	void push_in(double x);              //将数字压入栈
    	double push_out();                   //删除栈顶元素
    	void print_result();                 //打印运算完后的结果,也就是最后的栈顶元素
    private:
    	struct operate *top;
    };
    void new_linkstack::push_in(double in_number)
    {
    	struct operate *s;
    	s = new operate;
    	s->member = in_number;
    	s->next = top;
    	top = s;
    }
    double new_linkstack::push_out()
    {
    	struct operate *p;
    	if (top == NULL)throw"下溢";
    	double out_member;
    	out_member = top->member; p = top;
    	top = top->next;
    	delete p;
    	return out_member;
    }
    void new_linkstack::print_result()
    {
    	cout << top->member << endl;
    }
    int main()
    {
    	double x, y, result,b;
    	string new_a;
    	cin >> new_a;
    	new_linkstack one;
    	for (auto c = new_a.begin(); c != new_a.end(); c++) {   //从头到尾扫描new_a中的元素
    		if (isdigit(*c)) {              //如果当前元素为数字,直接入栈
    			stringstream sstream;
    			sstream << *c;
    			sstream >> b;              //string类型到double类型的转换
    			one.push_in(b);
    			sstream.clear();           //将stringstream流清空
    		}
    		else {                         //如果当前元素为运算符
    			x = one.push_out();        //将前两个栈顶的元素取出 
    			y = one.push_out(); 
    			switch (*c)                //new_a中的运算符不能直接用来做运算
    			{
    			case '+':
    				result = x + y; one.push_in(result); continue;//运算完后,将当前运算结果压入栈,进行下一个循环
    			case '-':
    				result = y - x; one.push_in(result); continue;
    			case '*':
    				result = x * y; one.push_in(result); continue;
    			case '/':
    				result = y / x; one.push_in(result); continue;
    			}
    		}
    	}
    	one.print_result();               //打印最终结果
    	system("pause");
    	return 0;
    }

    这样就将一个大的问题分成了两个小的问题,下边的代码是我合成之后的:

    # include <iostream>
    # include <string>
    # include <cctype>
    # include <sstream>
    using namespace std;
    struct sign
    {
    	char sign;
    	int level;
    	struct sign *next_1;
    };
    struct operate
    {
    	double member;
    	struct operate *next;
    };
    class new_linkstack
    {
    public:
    	new_linkstack() { top = NULL; }
    	void push_in(double x);
    	double push_out();
    	void print_result();
    private:
    	struct operate *top;
    };
    class linkstack
    {
    private:
    	struct sign *top;
    public:
    	linkstack() { top = NULL; }
    	char push_out();
    	void push_in(char new_sign);
    	char print_top();
    	int print_level();
    };
    int compare(char compared_sign)
    {
    	int level;
    	switch (compared_sign) {
    	case '(':
    		level = -10; break;
    	case ')':
    		level = -10; break;
    	case '+':
    		level = 0; break;
    	case '-':
    		level = 0; break;
    	case '*':
    		level = 1; break;
    	default:                         
    		level = 1; break;
    	}
    	return level;
    }
    char linkstack::print_top()
    {
    	char result;
    	result = top->sign;
    	return result;
    }
    int linkstack::print_level()
    {
    	return top->level;
    }
    char linkstack::push_out()
    {
    	char char_result;
    	struct sign *p;
    	char_result = top->sign;
    	p = top;
    	top = top->next_1;
    	delete p;
    	return char_result;
    }
    void linkstack::push_in(char new_sign)
    {
    	struct sign *s;
    	s = new struct sign;
    	s->sign = new_sign;
    	s->level = compare(new_sign);
    	s->next_1 = top;
    	top = s;
    }
    void new_linkstack::push_in(double in_number)
    {
    	struct operate *s;
    	s = new operate;
    	s->member = in_number;
    	s->next = top;
    	top = s;
    }
    double new_linkstack::push_out()
    {
    	struct operate *p;
    	if (top == NULL)throw"下溢";
    	double out_member;
    	out_member = top->member; p = top;
    	top = top->next;
    	delete p;
    	return out_member;
    }
    void new_linkstack::print_result()
    {
    	cout << top->member << endl;
    }
    int main()
    {
    	int count = 0; double m;
    	string a, b;
    	cin >> a;
    	linkstack one;
    	for (auto c = a.begin(); c != a.end(); c++) {
    		if (isdigit(*c)) {
    			b.push_back(*c);  continue;
    		}
    		else {
    			if (*c != ')'&&count == 0) {
    				one.push_in(*c);
    				count++;
    				continue;
    			}
    			if (*c == ')') {
    				while (one.print_top() != '(') {
    					b.push_back(one.print_top());
    					one.push_out(); count--;
    				}
    				one.push_out(); count--;
    				continue;
    			}
    			if (compare(*c) <= one.print_level()) {
    				b.push_back(one.print_top());
    				one.push_out();
    				one.push_in(*c);
    				continue;
    			}
    			if (compare(*c) > one.print_level()) {
    				one.push_in(*c); count++;
    				continue;
    			}
    		}
    	}
    	if (count) {
    		b.push_back(one.print_top());
    		one.push_out();
    	}
    	double x, y, result, new_b;
    	string new_a(b);
    	new_linkstack two;
    	for (auto c = new_a.begin(); c != new_a.end(); c++) {
    		if (isdigit(*c)) {
    			stringstream sstream;
    			sstream << *c;
    			sstream >> new_b;
    			two.push_in(new_b);
    			sstream.clear();
    		}
    		else {
    			x = two.push_out();
    			y = two.push_out();
    			switch (*c)
    			{
    			case '+':
    				result = x + y; two.push_in(result); continue;
    			case '-':
    				result = y - x; two.push_in(result); continue;
    			case '*':
    				result = x * y; two.push_in(result); continue;
    			case '/':
    				result = y / x; two.push_in(result); continue;
    			}
    		}
    	}
    	two.print_result();
    	system("pause");
    	return 0;
    }

    这也算是个人狭义上的第一次模块化的编程吧。。。。。。

    展开全文
  • 后缀表达式是计算机容易运算的表达式,运算符在运算数后面,从左到右进行运算,无需考虑优先级,运算呈线性结构. 先举个简单的转换例子 2+9/3-5 (前缀)-> 2 9 3 / + 5 - (后缀) 先进行乘除再进行加减 运算规律,.....

    中缀转后缀
    本文大部分资料参考慕课何钦铭老师的数据结构
    相关的慕课链接:表达式求值
    中缀表达式是最常用的算术表达式,运算符在运算数中间,运算需要考虑运算符优先级.
    后缀表达式是计算机容易运算的表达式,运算符在运算数后面,从左到右进行运算,无需考虑优先级,运算呈线性结构.
    先举个简单的转换例子
    2+9/3-5 (前缀)-> 2 9 3 / + 5 - (后缀)
    先进行乘除再进行加减
    运算规律,运算数位置不变,改变的是运算符位置
    可以推栈实现,用堆栈储存等待中的运算符.
    将当前运算符与最后一个等待的运算符比较.

    具体转换方式:
    1.从左到右进行遍历
    2.运算数,直接输出.
    3.左括号,直接压入堆栈,(括号是最高优先级,无需比较)(入栈后优先级降到最低,确保其他符号正常入栈)
    4.右括号,(意味着括号已结束)不断弹出栈顶运算符并输出直到遇到左括号(弹出但不输出)
    5.运算符,将该运算符与栈顶运算符进行比较,
    如果优先级高于栈顶运算符则压入堆栈(该部分运算还不能进行),
    如果优先级低于等于栈顶运算符则将栈顶运算符弹出并输出,然后比较新的栈顶运算符.
    (低于弹出意味着前面部分可以运算,先输出的一定是高优先级运算符,等于弹出是因为同等优先级,从左到右运算)
    直到优先级大于栈顶运算符或者栈空,再将该运算符入栈.
    6.如果对象处理完毕,则按顺序弹出并输出栈中所有运算符.

    再来解释一下开始的简单例子
    在这里插入图片描述
    括号的运算
    在这里插入图片描述
    选取慕课里何钦铭老师的案例
    在这里插入图片描述
    后缀表达式运算步骤:
    (以堆栈储存)
    从左到右,遇到运算符就弹出相应的运算数,运算后再把结果入栈.最终结果就是栈顶数的值.
    (由于该运算为线性结构,具体运算时是不需要储存输出后的运算符,一般是输出一个运算符就进行一次运算,不像图中要储存输出状态.)
    注意点:
    有时候’-’(负号)是单目运算符,则要修改运算数.
    遇到其他运算符(如幂运算)也类似.

    这篇文章只是整理中缀表达式转后缀表达式的方法和理论,目的是为了理解.
    具体代码实现看我的另一篇文章(模拟表达式运算).
    这部分转换对于初学者来说可能很模糊,建议去看开头链接的那个视频.
    如果有什么错误或不足欢迎评论指出.

    展开全文
  • 中缀表达式转后缀表达式的方法

    万次阅读 多人点赞 2020-08-03 22:13:54
    表达式求值: 1.从左到右进行遍历 2.运算数,直接输出. 3.左括号,直接压入堆栈,(括号是最高优先级,无需比较)(入栈后优先级降到最低,确保其他符号正常入栈) 4.右括号,(意味着括号已结束)不断弹出栈顶运算符并输出直到...
  • 中缀转后缀表达式并计算
  • 后缀表达式(逆波兰表达式):机器熟悉的算术表达式,如:3 4 + 5 * 6 - 8 + 1. 中缀转前缀语言描述:从右向左遍历中缀表达式,如果是数字就压入数字栈,如果是符号就压入符号栈,如果当前符号比符号栈栈顶符号...
  • 中缀表达式转后缀表达式思路步骤分析 一、初始化两个栈: 运算符栈symbolStack 和 存储中间结果的栈 resultStack; 二、从左到右扫描中缀表达式; 三、遇到操作数时,将其压入到 resultStack中; 四、遇到运算符时,...
  • 安装Parser Generator软件,熟悉其使用,对讲义中简单表达式计算的Yacc...3.修改Yacc程序,不进行表达式的计算,而是实现中缀表达式到后缀表达式的转换。 C语言版,包含.y和对应的两个.h,.c文件,在VS2013上编译成功。
  • 一个编译原理中缀转后缀表达式(递归下降翻译成AST,后序遍历得到后缀)的 Java 程序,读取文件中的中缀表达式(每个表达式以分号结束,文件中可以有多个表达式)并转换为等价的后缀表达式后输出到屏幕上, 表达式中...
  • 首先中缀表达式转后缀表达式(逆波兰表达式)需要用到一个栈来辅助实现。下面有几条规则(抄的网友的,哈哈哈自己也重新整理了一下) 具体转换方式: 首先的优先级我把它分为( > ÷ > × > - > + 将...
  • 表达式2*(9+6/3-5)+4,称为中缀表达式,表示成2 9 6 3 / + 5 - * 4 +称为后缀表达式,表示成+ * 2 - + 9 / 6 3 5 4称为前缀表达式。 ·基本要求 将中缀表达式,转换为后缀表达式和前缀表达式,再分别计算转换后的...
  • 后缀表达式:计算机喜欢的形式,没有括号所有符号都是在要运算的数字后面出现。 因为计算机是用栈来计算的,其规则为:从左到右扫描表达式中的每个数字和符号,遇到数字就进栈,遇到符号就将处于栈顶的两个数字...
  • 该程序实现了运算表达式转换为中缀表达式、中缀表达式转换为后缀表达式后缀表达式求值。该程序已实现加减乘除括号运算符及求余、幂指数的求解
  •  中缀表达式就是我们通常所书写的数学表达式,后缀表达式也称为逆波兰表达式,在编译程序对我们书写的程序中的表达式进行语法检查时,往往就可以通过逆波兰表达式进行。我们所要设计并实现的程序就是将中缀表示的...
  • 中缀表达式转后缀表达式并求值(多位数) 一、问题简述 中缀表达式:是一种通用的算术或逻辑公式表示方法,操作符处于操作数的中间。中缀表达式是人们常用的算术表示方法,如3+5*8。 后缀表达式(逆波兰表达式):...
  • 我们的表达式可以分为中缀表达式、前缀表达式、后缀表达式。在我们的上一篇博客中说了用Java栈来模拟实现综合计算器,在哪个算法中我们传递给程序的实际是中缀表达式,也就是我们最常见的表达式形式——操作符位于两...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,742
精华内容 6,696
关键字:

中缀转后缀表达式过程