中缀表达式转后缀表达式
思路分析:
初始化两个栈:运算符栈s1 和储存中间结果的栈s2从左至右扫描中缀表达式遇到操作数,将其压入s2遇到运算符时,比较其与s1 栈顶运算符的优先级 如果s1 为空,或栈顶运算符位左括号(
,则直接将此运算符入栈若优先级比栈顶运算符的高,也将运算符压入s1否则,将s1 栈顶的运算符弹出并压入到s2 中,再次转换(4-1)与s1中新的栈顶运算符相比较 遇到括号时: 如果是左括号(
,则直接压入s1如果是右括号)
,则依次弹出s1 栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃 重复执行2至5步,直到表达式的最右边将s1 中剩余的运算符依次弹出并压入s2一次弹出s2 中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式
//实现中缀转后缀功能public static List<String> Infix2Suffix(String infixexpression){//定义一个InList存放中缀表达式的内容List<String> InList = new ArrayList<String>();int index = 0;//用于扫描char ch = ' ';//将每次扫描得到char保存到chString str;//对多位数拼接//一、将infixexpression中的值存入InList中do{//如果ch是一个非数字if((ch=infixexpression.charAt(index)) < 48 || (ch=infixexpression.charAt(index)) > 57){InList.add("" + ch);index++;//index后移}else {//如果是一个数字,需要考虑多位数str = "";//将str置为空while(index < infixexpression.length() && (ch=infixexpression.charAt(index)) >= 48 && (ch=infixexpression.charAt(index)) <= 57){str += ch;//拼接多位数index++;}InList.add(str);}}while (index < infixexpression.length());//二、将InList中的值转为后缀表达式//初始化两个栈,运算符栈s1,存储中间结果的栈s2Stack<String> s1 = new Stack<String>();//说明:由于s2栈中元素不参与pop操作,且最后返回值为逆序,所以用List代替List<String> s2 = new ArrayList<String>();//遍历InListfor(String item: InList){//用正则表达式判断if(item.matches("\\d+")){//如果是一个数,直接加入s2s2.add(item);}else if(item.equals("(")){//如果是左括号,直接压入s1s1.push(item);}else if(item.equals(")")){//如果是右括号`)`,则依次弹出s1 栈顶的运算符,并压入s2//直到遇到左括号为止,此时将这一对括号丢弃while(!s1.peek().equals("(")){s2.add(s1.pop());}s1.pop();//将(弹出s1,消除小括号}else{//当item的优先级小于等于栈顶元素优先级//将s1栈顶的运算符弹出并加入到s2中//再次与s1中新的栈顶运算符比较while(s1.size() != 0 && priority(s1.peek()) >= priority(item)){s2.add(s1.pop());}//还需要将item入栈s1.push(item);}}//将s1中剩余的运算符依次弹出并加入s2while(s1.size() != 0){s2.add(s1.pop());}//由于存放在List,因此按顺序输出就是对应的后缀表达式return s2;}
判断运算符优先级
//创建一个方法,返回运算符的优先级public static int priority(String oper){if(Objects.equals(oper, "*") || Objects.equals(oper, "/")){return 2;}else if(Objects.equals(oper, "+") || Objects.equals(oper, "-")){return 1;}else{return -1;//假定目前表达式只含有+,-,*,/}}
逆波兰计算器(后缀表达式的计算)
后缀表达式的计算机求值思路:
从左到右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对他们做相应的计算(次顶元素和栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果例如:(3+4)*5-6
对应的后缀表达式就是3 4 + 5 * 6 -
,步骤如下: 从左至右扫描,将3和4压入栈堆遇到+
操作符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算3+4的值,得7,再将7入栈将5入栈接下来是*
运算符,因此弹出5和7,计算出7*5 = 35,将35入栈将6入栈最后是-
运算符,计算出35-6的值,即29,由此得出最终结果
//完成对逆波兰表达式的运算public static int calculator(List<String> ls){//创建堆栈,只需要一个即可Stack<String> stack = new Stack<String>();//遍历lsfor(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;switch (item){case "+":res = num1 + num2;break;case "-":res = num1 - num2;break;case "*":res = num1 * num2;break;case "/":res = num1 / num2;break;default:throw new RuntimeException("运算符有误!!!");}//把res入栈//将整型转为字符串的简单操作stack.push(res + "");}}//最后留在stack中的数据就是运算结果//注意将符号转为整型return Integer.parseInt(stack.pop());}
完整代码
package com.crisp.Stack;import java.util.ArrayList;import java.util.List;import java.util.Objects;import java.util.Stack;public class RePolishNotation {public static void main(String[] args) {//测试完整功能String expression = "1+((2+3)*4)-5";System.out.printf("%s 对应的后缀表达式为:",expression);System.out.println(Infix2Suffix(expression));System.out.printf("%s = %d\n",expression,calculator(Infix2Suffix(expression)));}//实现中缀转后缀功能public static List<String> Infix2Suffix(String infixexpression){//定义一个InList存放中缀表达式的内容List<String> InList = new ArrayList<String>();int index = 0;//用于扫描char ch = ' ';//将每次扫描得到char保存到chString str;//对多位数拼接//一、将infixexpression中的值存入InList中do{//如果ch是一个非数字if((ch=infixexpression.charAt(index)) < 48 || (ch=infixexpression.charAt(index)) > 57){InList.add("" + ch);index++;//index后移}else {//如果是一个数字,需要考虑多位数str = "";//将str置为空while(index < infixexpression.length() && (ch=infixexpression.charAt(index)) >= 48 && (ch=infixexpression.charAt(index)) <= 57){str += ch;//拼接多位数index++;}InList.add(str);}}while (index < infixexpression.length());//二、将InList中的值转为后缀表达式//初始化两个栈,运算符栈s1,存储中间结果的栈s2Stack<String> s1 = new Stack<String>();//说明:由于s2栈中元素不参与pop操作,且最后返回值为逆序,所以用List代替List<String> s2 = new ArrayList<String>();//遍历InListfor(String item: InList){//用正则表达式判断if(item.matches("\\d+")){//如果是一个数,直接加入s2s2.add(item);}else if(item.equals("(")){//如果是左括号,直接压入s1s1.push(item);}else if(item.equals(")")){//如果是右括号`)`,则依次弹出s1 栈顶的运算符,并压入s2//直到遇到左括号为止,此时将这一对括号丢弃while(!s1.peek().equals("(")){s2.add(s1.pop());}s1.pop();//将(弹出s1,消除小括号}else{//当item的优先级小于等于栈顶元素优先级//将s1栈顶的运算符弹出并加入到s2中//再次与s1中新的栈顶运算符比较while(s1.size() != 0 && priority(s1.peek()) >= priority(item)){s2.add(s1.pop());}//还需要将item入栈s1.push(item);}}//将s1中剩余的运算符依次弹出并加入s2while(s1.size() != 0){s2.add(s1.pop());}//由于存放在List,因此按顺序输出就是对应的后缀表达式return s2;}//创建一个方法,返回运算符的优先级public static int priority(String oper){if(Objects.equals(oper, "*") || Objects.equals(oper, "/")){return 2;}else if(Objects.equals(oper, "+") || Objects.equals(oper, "-")){return 1;}else{return -1;//假定目前表达式只含有+,-,*,/}}//完成对逆波兰表达式的运算public static int calculator(List<String> ls){//创建堆栈,只需要一个即可Stack<String> stack = new Stack<String>();//遍历lsfor(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;switch (item){case "+":res = num1 + num2;break;case "-":res = num1 - num2;break;case "*":res = num1 * num2;break;case "/":res = num1 / num2;break;default:throw new RuntimeException("运算符有误!!!");}//把res入栈//将整型转为字符串的简单操作stack.push(res + "");}}//最后留在stack中的数据就是运算结果//注意将符号转为整型return Integer.parseInt(stack.pop());}}
该算法来自
BV1E4411H73v
,博主稍加整理改进