中缀表达式转后缀表达式
思路分析：
初始化两个栈：运算符栈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，博主稍加整理改进
