大家看到,后缀表达式适合计算机进行运算,但是人却不容易写出,尤其是表达式 很长的情况,因此在开发中,我们需要将中缀表达式转成后缀表达式。 具体步骤如下(注意小括号不算运算符,因此不比较运算符优先级): 1.初始化两个栈,运算符栈s1和存储中间结果的栈s2 2.从左至右扫描中缀表达式 3.遇到 *** 作数时,将其压s2 4.遇到运算符时,比较其与s1栈顶运算符的优先级 a.如果s1为空,或栈顶运算符为左括号"(",则直接将此运算符入栈 b.否则,若优先级比栈顶运算符的高,也将运算符压如s1 c.否则,将s1栈顶的运算符d出并压入到s2中,再次转到(4-a)与s1中新的 栈顶运算符相比较 5.遇到括号时: a.如果是左括号"(",则直接压入s1 b.如果是右括号")",则依次d出s1栈顶的运算符,并压入s2,直到遇到左括号 为止,此时将这一对括号丢弃。 6.重复步骤2至5,直到表达式的最右边 7.将s1中剩余的运算符依次d出并压入s2 8.依次d出s2中的元素并输入,结果的逆序即为中缀表达式对应的后缀表达式。 中缀表达式 1 + ( ( 2 + 3 ) * 4 ) - 5 --> 后缀表达式 将s2出栈 - 5 + * 4 + 3 2 1 --> 1 2 3 + 4 * + 5 - 技能学习步骤:学习-->应用 算法学习步骤: 第一层:理解-->灵活运用来解决问题 第二层:设计算法--> 运用算法
表格示意如下:
中缀转后缀表达式图解如下:
中缀表达式转后缀表达式代码如下:
public class PolandNotation { public static void main(String[] args) { // TODO Auto-generated method stub // 完成将一个中缀表达式转成后缀表达式的功能 // 说明 // 1. 1+((2+3)x4)-5 => 转成 1 2 3 + 4 x + 5 // 2.因为直接对一个字符串进行 *** 作不方面,先将字符串"1+((2+3)x4)-5"转成中缀表达式对应的list // 即"1+((2+3)x4)-5" => ArrayList[1, +, (, (, 2, +, 3, ), x, 4, ), -, 5] // 3.将得到的中缀表达式对应的List-> 后缀表达式对应的List // 即ArrayList[1, +, (, (, 2, +, 3, ), x, 4, ), -, 5] // --> ArrayList [1, 2, 3, +, 4, x, +, 5, -]小括号已经被消除 String expression = "1+((2+3)*4)-5"; ListinfixexpressionList = toInfixexpressionList(expression); // ArrayList[1, +, (, (, 2, +, 3, ), x, 4, ), -, 5] System.out.println("中缀表达式对应的List=" + infixexpressionList); List suffixexpressionList = parseSuffixexpressionList(infixexpressionList); System.out.println("后缀表达式对应的List=" + suffixexpressionList); System.out.printf("expression = %d", calculate(suffixexpressionList)); } // 即ArrayList[1, +, (, (, 2, +, 3, ), x, 4, ), -, 5] // --> ArrayList [1, 2, 3, +, 4, x, +, 5, -]小括号已经被消除 // 方法:将得到的中缀表达式对应的List --> 后缀表达式对应的List public static List parseSuffixexpressionList(List ls) { // 定义两个栈 Stack s1 = new Stack (); // s1符号栈 // 因为s2在整个转换过程中,没有pop *** 作,而且后面还需要 // 逆序输出,因此麻烦,直接使用List List s2 = new ArrayList (); // s2存储中间结果的list栈 // 遍历ls for (String item : ls) { // 如果是一个数,加入到s2 if (item.matches("\d+")) { s2.add(item); } else if (item.equals("(")) { s1.push(item); } else if (item.equals(")")) {// 如果是右括号")",则依次d出s1栈顶的运算符,并压入s2, // 直到遇到左括号为止,此时将这一对括号丢弃 while (!s1.peek().equals("(")) { s2.add(s1.pop()); } // 将(d出s1栈,消除小括号 s1.pop(); } else { // 当item的优先级小于等于s1栈顶运算符,将s1栈顶的运算符d出并压入s2中, // 再次转到(4.a)与s1中新的栈顶运算符的相比较 // 问题:我们缺少一个比较优先级高低的方法 while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) { s2.add(s1.pop()); } // 还需要将item压入栈 s1.push(item); } } // 将s1中剩余的运算符依次d出并压入s2 while (s1.size() != 0) { s2.add(s1.pop()); } return s2; // 注意因为是存放到List,因此按顺序输出就是对应的后缀表达式对应的List } // 方法:将中缀表达式转成对应的List public static List toInfixexpressionList(String s) { // 定义一个List,存放中缀表达式对应的内容 List ls = new ArrayList (); int i = 0; // 一个用于遍历中缀表达式字符串的指针 String str; // 对多位数的拼接 char c; // 每遍历到一个字符就放入到c do { // 如果c是一个非数字,需要加入到ls if ((c=s.charAt(i)) < 48 || (c=s.charAt(i)) > 57) { ls.add("" + c); i++; } else { // 如果是一个数,需要考虑多位数 str = ""; // 先将str 重置成空字符串 '0'[48]->'9'[57] while (i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57) { str += c; // 拼接 i++; } ls.add(str); } } while (i < s.length()); return ls; // 返回ls } // 将一个逆波兰表达式,依次将数据和运算符放入到ArrayList中 public static List getListString(String suffixexpression) { // 将suffixexpression分割 String[] split = suffixexpression.split(" "); List list = new ArrayList (); for (String ele : split) { list.add(ele); } return list; } // 完成对逆波兰表达式的计算 public static int calculate(List ls) { // 创建一个栈即可 Stack stack = new Stack (); // 遍历ls for (String item : ls) { // 使用正则表达式取数 if (item.matches("\d+")) {// 匹配的是多位数 // 直接入栈 stack.push(item); } else { // pop出两个数,并运算,再入栈 int num2 = Integer.parseInt(stack.pop()); int num1 = Integer.parseInt(stack.pop()); int res = 0; if (item.equals("+")) { res = num1 + num2; } else if (item.equals("-")) { res = num1 - num2; } else if (item.equals("*")) { res = num1 * num2; } else if (item.equals("/")) { res = num1 / num2; } else { throw new RuntimeException("运算符错误~"); } // 把res入栈 stack.push(res + ""); } } // 最后留在stack中的数据是运算结果 return Integer.parseInt(stack.pop()); } } // 编写一个类,Operation 可以返回一个运算符对应的优先级 class Operation { private static int ADD = 1; private static int SUB = 1; private static int MUL = 2; private static int DIV = 2; // 写一个方法,返回对应的优先级数字 public static int getValue(String operation) { int result = 0; switch (operation) { case "+": result = ADD; break; case "-": result = SUB; break; case "*": result = MUL; break; case "/": result = DIV; break; default: System.out.println("不存在该运算符"); break; } return result; } } 上述代码的总结: 为什么要先将中缀字符串表达式转换成List? 因为这样后续 *** 作的时候更加方便(哪里方便?) 后续遍历更加方便,无需多余的指针辅助 为什么要用s1 s2两个栈来转换中缀成后缀? 因为一个s2直接作为后缀的容器,而s1作为中间 容器,其作用是安排运算符和括号顺序 为什么使用List作为后缀表达式栈? 因为后缀表达式是从左到右的顺序来进行运算的 逆波兰计算器完整版: 完整版的逆波兰计算器,功能包括: 1.支持+ - * / ( ) 2.多位数,支持小数 3.兼容处理,过滤任何空白字符,包括空格,制表符,换页符 逆波兰计算器完整版考虑的因素较多,下面给出完整版代码供同学学习, 其基本思路和前面一样,也是使用到:中缀表达式转后缀表达式
需要代码实现
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)