精华内容
下载资源
问答
  • 题目: 问题描述  输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。 输入格式  输入一行,包含一个表达式。 输出格式  输出这个表达式的值。...中缀表达式转后缀表达式的方法: 1.遇到
    

    题目:

    问题描述
      输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。
    输入格式
      输入一行,包含一个表达式。
    输出格式
      输出这个表达式的值。
    样例输入
    1-2+3*(4-5)
    样例输出
    -4
    数据规模和约定
      表达式长度不超过100,表达式运算合法且运算过程都在int内进行。


    中缀表达式转后缀表达式的方法:
    1.遇到操作数:直接输出(添加到后缀表达式中)
    2.栈为空时,遇到运算符,直接入栈
    3.遇到左括号:将其入栈
    4.遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出。
    5.遇到其他运算符:加减乘除:弹出所有优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈
    6.最终将栈中的元素依次出栈,输出。

    后缀表达式的计算机求值:
    与前缀表达式类似,只是顺序是从左至右:
    从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。


    public class Main {
    
    	/**
    	 * 中缀表达式变为后缀表达式:(1+2)*((8-2)/(7-4)) 
    	 * 遇到操作数,直接输出,并输出一个空格
    	 * 若遇到运算符,则必须与栈顶比较,运算符级别比栈顶级别高则进栈,否则退出栈顶元素并输出
    	 * 若遇到左括号,进栈;若遇到右括号,则一直退栈输出,直到退到左括号止
    	 */
    	public static void main(String[] args) {
    		System.out.println(compute(new Main().transfer("(1+2)*((8-2)/(7-4))")));
    		
    	}
    	/*
    	 * 计算:
    	 * 到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,
    	 * 用运算符对它们做相应的计算,并将结果入栈;
    	 */
    	public static int compute(String s) { // 计算后缀表达式的值
    		Stack<Integer> stack = new Stack<Integer>();
    		char[] array = s.trim().toCharArray();
    		for (int i = 0; i < array.length && array[i] != ' '; i++) {
    			if (array[i] >= '0' && array[i] <= '9') {
    				int n = 0;
    				while (array[i] >= '0' && array[i] <= '9') {
    					n = n * 10 + Integer.parseInt(array[i] + "");
    					i++;
    				}
    				i--;
    			} else {
    				if (stack.size() >= 2) {
    					int num1 = stack.pop();
    					int num2 = stack.pop();
    					stack.push(cal(num1, num2, array[i]));
    				}
    			}
    		}
    		if (!stack.isEmpty()) {
    			return stack.pop();
    		}
    		return -1;
    	}
    	public static String transfer(String s) {
    		String res = "";
    		Stack<Character> stack = new Stack<Character>();
    		for (int i = 0; i < s.length(); i++) {
    			char a = s.charAt(i);
    			if (a != ' ') {
    				if (a >= '0' && a <= '9') {
    					res += a;
    					res += " ";
    				}else if (a == ')') {
    					while (stack.peek() != '(') {
    						res += stack.pop();
    						res += " ";
    					}
    					stack.pop();
    				} else {
    					if (a != '(') {
    						if(!stack.isEmpty() && isType(stack.peek()) >= isType(a)) {
    							res += stack.pop();
    							stack.push(a);
    							break;
    						}
    					}
    					stack.push(a);
    				}
    			}
    		}
    		if (!stack.isEmpty()) {
    			res += stack.pop();
    		}
    		return res;
    	}
    	public static int isType(char c) { // 返回运算符的优先级
    		if (c == '+' || c == '-') {
    			return 1;
    		} else if (c == '*' || c == '/') {
    			return 2;
    		} else {
    			return  0;
    		}
    	}
    	public static int cal (int m, int n, char c) {
    		int sum = 0;
    		if (c == '+') {
    			sum = m + n;
    		} else if (c =='-') {
    			sum = m - n;
    		} else if (c =='*') {
    			sum = m * n;
    		} else if (c =='/') {
    			sum = m / n;
    		}
    		return sum;
    	}
    }


    原文链接:

    http://www.cnblogs.com/16crow/p/6545126.html


    展开全文
  • 1、若 A=10 , B=4 , C=6 , D=4 , E=15 则后缀表达式“ AB*CD±E+ ”的值为 ( ) 。 后缀表达式求值的规则:从左到右遍历表达式的每个字符和符号,遇到数字就进栈,遇到是符号就将栈顶的两个数字出栈并计算,将...

    《数据结构打卡》第11天

    还没想到今天写点啥呢,今天的10个英语单词都没有背完,难受啊,昨天背的单词今天也只记得零星的几个了。

    1、若 A=10 , B=4 , C=6 , D=4 , E=15 则后缀表达式“ AB*CD±E+ ”的值为 ( ) 。
    后缀表达式求值的规则:从左到右遍历表达式的每个字符和符号,遇到数字就进栈,遇到是符号就将栈顶的两个数字出栈并计算,将计算结果再进栈,一直到最终获得结果。

    2、对数据序列{ 15,9,7,8,20,-1,4 }进行排序,进行一趟后数据的排序变为{ 9,15,7,8,20,-1,4 } ,则采用的是( )算法。
    1.选择排序是每次选择未排序子列中最大(最小)的放到最后,显然4不是最值,所以A不对;
    2.冒泡排序是相邻两两比较,把最大的顶上去,显然边上两个元素不是最值,所以B也不对;
    3.希尔排序是先分组,然后针对组内采取插入排序,如果是希尔排序,那么9和15颠倒,20和-1也应该颠倒,所以D也不对;
    排除下来选C。
    插入排序是从第二项开始与前面每一项比较,如果小于那一项,则插入那一项前面,C中第二项9比15小,所以放到15前面。

    展开全文
  • 文章目录前缀表达式(波兰表达式)前缀表达式分析与介绍思路分析中缀表达式中缀表达式分析与介绍后缀表达式(逆波兰表达式)后缀表达式分析与介绍思路分析逆波兰计算器代码实现逆波兰计算器中缀表达式转换后缀...
  • 认识前缀、中缀后缀表达式: 一般我们平时用的计算式都是中缀表达式,因为符号都是在操作数的中间的。相对应的符号在操作数后面的就叫后缀表达式(也称逆波兰式),符号在操作数前面的就叫前缀表达式(也称波兰式)...

    认识前缀、中缀、后缀表达式:
    一般我们平时用的计算式都是中缀表达式,因为符号都是在操作数的中间的。相对应的符号在操作数后面的就叫后缀表达式(也称逆波兰式),符号在操作数前面的就叫前缀表达式(也称波兰式)。


    为什么要把中缀表达式转化为后缀,前缀?

    计算机没法计算带有括号,以及区分优先级的表达式,或者说很难计算。使用后缀,前缀,消除了括号和优先级。

    计算机如何计算后缀,前缀表达式?

    计算后缀:从左到右遍历后缀表达式,遇到操作数,放进栈,遇到操作符,栈顶两个数出栈,进行运算,运算结果放进栈,直到读完后缀表达式。

    计算前缀:从左到右遍历前缀表达式,遇到操作符,放进栈,遇到操作数,查看栈顶,栈顶为操作符,放进栈,栈顶为操作数,取出栈顶操作数和操作符,进行运算,运算后继续判断栈顶的情况。

    中缀表达式转换成前缀表达式

    (1)构建两个栈,一个存运算符一个存操作数。运算符(以括号分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列。

    (2)从右至左扫描中缀表达式,从右边第一个字符开始判断:

    如果当前字符是数字,则分配到数字串的结尾并将数字串直接输出。

    如果是运算符,则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时,直接入栈),则将运算符直接入栈;否则将栈顶运算符出栈并输出,直到当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时,直接入栈),再将当前运算符入栈。如果是括号,则根据括号的方向进行处理。如果是右括号,则直接入栈;否则,遇右括号前将所有的运算符全部出栈并输出,遇右括号后将左右的两括号一起删除。

    (3) 重复上述操作(2)直至扫描结束,将栈内剩余运算符全部出栈并输出,再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。

    中缀表达式转换成后缀表达式

    中缀表达式转换成前缀表达式相似


    参考:
    前缀—中缀–后缀 表达式的相互转换 https://blog.csdn.net/linsheng9731/article/details/23125353
    表达式转化(中缀,后缀,前缀) https://www.cnblogs.com/nzbbody/p/3335226.html
    将中缀表达式转换成后缀表达式 https://www.cnblogs.com/chenjiafeng/p/5328578.html
    前缀、中缀、后缀表达式及中缀转后缀表达式 https://blog.csdn.net/kobe_jr/article/details/80377836

    展开全文
  • 它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数...3 4 + 5 × 6 - 后缀表达式 中缀表达式(中缀记法) 中缀表达式是一种通用的算术或逻辑公式表示方法

    它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数的位置不同:前缀表达式的运算符位于与其相关的操作数之前;中缀和后缀同理。


    举例:
    (3 + 4) × 5 - 6 就是中缀表达式
    - × + 3 4 5 6 前缀表达式
    3 4 + 5 × 6 - 后缀表达式

    中缀表达式(中缀记法)
    中缀表达式是一种通用的算术或逻辑公式表示方法,操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。
    虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀或后缀表达式,然后再进行求值。对计算机来说,计算前缀或后缀表达式的值非常简单。

    前缀表达式(前缀记法、波兰式)
    前缀表达式的运算符位于操作数之前。

    前缀表达式的计算机求值:
    从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。
    例如前缀表达式“- × + 3 4 5 6”:
    (1) 从右至左扫描,将6、5、4、3压入堆栈;
    (2) 遇到+运算符,因此弹出3和4(3为栈顶元素,4为次顶元素,注意与后缀表达式做比较),计算出3+4的值,得7,再将7入栈;
    (3) 接下来是×运算符,因此弹出7和5,计算出7×5=35,将35入栈;
    (4) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。
    可以看出,用计算机计算前缀表达式的值是很容易的。

    将中缀表达式转换为前缀表达式:
    遵循以下步骤:
    (1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
    (2) 从右至左扫描中缀表达式;
    (3) 遇到操作数时,将其压入S2;
    (4) 遇到运算符时,比较其与S1栈顶运算符的优先级:
    (4-1) 如果S1为空,或栈顶运算符为右括号“)”,则直接将此运算符入栈;
    (4-2) 否则,若优先级比栈顶运算符的较高或相等,也将运算符压入S1;
    (4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
    (5) 遇到括号时:
    (5-1) 如果是右括号“)”,则直接压入S1;
    (5-2) 如果是左括号“(”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到右括号为止,此时将这一对括号丢弃;
    (6) 重复步骤(2)至(5),直到表达式的最左边;
    (7) 将S1中剩余的运算符依次弹出并压入S2;
    (8) 依次弹出S2中的元素并输出,结果即为中缀表达式对应的前缀表达式。
    例如,将中缀表达式“1+((2+3)×4)-5”转换为前缀表达式的过程如下:
    扫描到的元素 S2(栈底->栈顶) S1 (栈底->栈顶) 说明
    5 5 数字,直接入栈
    - 5 - S1为空,运算符直接入栈
    ) 5 - ) 右括号直接入栈
    4 5 4 - ) 数字直接入栈
    × 5 4 - ) × S1栈顶是右括号,直接入栈
    ) 5 4 - ) × ) 右括号直接入栈
    3 5 4 3 - ) × ) 数字
    + 5 4 3 - ) × ) + S1栈顶是右括号,直接入栈
    2 5 4 3 2 - ) × ) + 数字
    ( 5 4 3 2 + - ) × 左括号,弹出运算符直至遇到右括号
    ( 5 4 3 2 + × - 同上
    + 5 4 3 2 + × - + 优先级与-相同,入栈
    1 5 4 3 2 + × 1 - + 数字
    到达最左端 5 4 3 2 + × 1 + - S1中剩余的运算符
    因此结果为“- + 1 × + 2 3 4 5”。

    后缀表达式(后缀记法、逆波兰式)
    后缀表达式与前缀表达式类似,只是运算符位于操作数之后。

    后缀表达式的计算机求值:
    与前缀表达式类似,只是顺序是从左至右:
    从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
    例如后缀表达式“3 4 + 5 × 6 -”:
    (1) 从左至右扫描,将3和4压入堆栈;
    (2) 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素,注意与前缀表达式做比较),计算出3+4的值,得7,再将7入栈;
    (3) 将5入栈;
    (4) 接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈;
    (5) 将6入栈;
    (6) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。

    将中缀表达式转换为后缀表达式:
    与转换为前缀表达式相似,遵循以下步骤:
    (1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
    (2) 从左至右扫描中缀表达式;
    (3) 遇到操作数时,将其压入S2;
    (4) 遇到运算符时,比较其与S1栈顶运算符的优先级:
    (4-1) 如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
    (4-2) 否则,若优先级比栈顶运算符的高,也将运算符压入S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);
    (4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
    (5) 遇到括号时:
    (5-1) 如果是左括号“(”,则直接压入S1;
    (5-2) 如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃;
    (6) 重复步骤(2)至(5),直到表达式的最右边;
    (7) 将S1中剩余的运算符依次弹出并压入S2;
    (8) 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。

    例如,将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下:
    扫描到的元素 S2(栈底->栈顶) S1 (栈底->栈顶) 说明
    1 1 数字,直接入栈
    + 1 + S1为空,运算符直接入栈
    ( 1 + ( 左括号,直接入栈
    ( 1 + ( ( 同上
    2 1 2 + ( ( 数字
    + 1 2 + ( ( + S1栈顶为左括号,运算符直接入栈
    3 1 2 3 + ( ( + 数字
    ) 1 2 3 + + ( 右括号,弹出运算符直至遇到左括号
    × 1 2 3 + + ( × S1栈顶为左括号,运算符直接入栈
    4 1 2 3 + 4 + ( × 数字
    ) 1 2 3 + 4 × + 右括号,弹出运算符直至遇到左括号
    - 1 2 3 + 4 × + - -与+优先级相同,因此弹出+,再压入-
    5 1 2 3 + 4 × + 5 - 数字
    到达最右端 1 2 3 + 4 × + 5 - S1中剩余的运算符

    因此结果为“1 2 3 + 4 × + 5 -”(注意需要逆序输出)。
    展开全文
  • Infix expression invert to Reverse Polish expression前缀表达式(Polish expression, 波兰表达式)中缀表达式(Infix expression)后缀表达式(Reverse Polish expression, 逆波兰表达式)中缀表达式(Infix expression...
  • 中缀表达式转换后缀表达式

    万次阅读 多人点赞 2017-04-22 11:50:10
    一、后缀表达式求值 后缀表达式也叫逆波兰表达式,其求值过程可以用到栈来辅助存储。假定待求值的后缀表达式为:6 5 2 3 + 8 * + 3 + *,则其求值过程如下: 1)遍历表达式,遇到的数字首先放入栈中,此时栈如下所...
  • 前缀中缀后缀表达式及其互相转换

    万次阅读 2015-05-24 19:59:02
    计算机中前缀中缀后缀表达式是数据结构栈的重要应用,他们都是对表达式的记法,只是相对位置不一样,顾名思义,前缀表达式指的是符号都在操作数之前,中缀表达式指的是运算符都在操作数之后,而后缀表达式是之后。...
  • 3、从右至左扫描中缀表达式,如果是数字,就直接压入结果栈 若是运算符,则与运算符栈顶元素比较优先级:若该运算符优先级大于等于栈顶元素,则将该运算符入栈 否则栈内元素出栈并压入结果栈,再与其比较,直到该...
  • 虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀或后缀表达式,然后再进行求值。对计算机来说,计算前缀或后缀表达式的值...
  • 中缀表达式转换后缀表达式(oj题库) 中缀表达式转换后缀表达式(oj题库) 题目描述 中缀表达式是一个通用的算术或逻辑公式表示方法,操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的...
  • 计算后缀表达式只用到一个栈,因此很多情况下需要将中缀表达式转换后缀表达式,以方便进行计算。 使用条件:只能出现二元操作符加减乘除,不能出现负号等一元操作符 1. 如果中缀表达式以全括号形式表示,则可以...
  • 08.中缀表达式转换后缀表达式算法.ppt
  • 请设计程序将中缀表达式转换后缀表达式。 输入格式: 输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。 输出格式: 在一行中输出转换后的后缀表达式,要求不同对象...
  • 35,15,+,80,70,-,*,20,/ //后缀表达方式(((35+15)*(80-70))/20)=25 //中缀表达方式 /,*,+,35,15,-,80,70, 20 //前缀表达方式 人的思维方式很容易固定!正如习惯拉10进制。就对2,3,4,8,16等进制不知所措...
  • 中缀表达式转后缀表达式前言需求分析程序功能主要函数源代码结语 前言 中缀表达式就是生活中习惯看到的表达式,知道学习数据结构的时候我才知道原来还有前缀表达式和后缀表达式。因为这些表达式看着很奇怪。但是仔细...
  • 三个方法: ① 将中缀表达式转换中缀表达式对应的 List ② 自定义运算符优先级 ???? 将中缀表达式对应的 list 转换成 后缀表达式. 1.1 使用 list 更好的和 stack 配合,list 比 字符串的遍历更加灵活. 将中缀...
  • 前缀、中缀后缀表达式转换详解

    万次阅读 多人点赞 2019-03-20 18:04:40
    1、中缀表达式 转 后缀表达式 2、中缀表达式 转 前缀表达式 3、后缀表达式中缀表达式 1、中缀表达式转后缀表达式的两种方法: 假定有中缀表达式A:1 + (( 2 + 3)* 4 ) – 5,请将它转化为后缀表达式。 ...
  • c语言实现中缀表达式向后缀表达式转换 分类:算法+数据结构
  • 1.中缀表达式转换后缀表达式: 首先需要注意的是:中缀转后缀的结果并不唯一。例如:(a+b+c*d)/e是一个中缀表达式,ab+cd*+e/与abcd*++e/都是其后缀表达式。 转换方式:先根据中缀表达式的各操作符的优先级,...
  • } } 5、使用堆栈,将中缀算术表达式转换后缀表达式。 A、表达式中只有+、-、×,/,%,(,)六种运算符 B、变量名为以英文字母开头的字母数字串 C、表达式中可以出现不带符号的常数 D、适当判断表达式中的...
  • 本程序用c++编写,实现中缀表达式向后缀表达式转换 其中,中缀表达式的操作数是一位
  • 该程序实现了运算表达式转换中缀表达式、中缀表达式转换后缀表达式后缀表达式求值。该程序已实现加减乘除括号运算符及求余、幂指数的求解

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,883
精华内容 1,153
关键字:

中缀后缀表达式转换