package com.guigu.stack;import com.sun.image.codec.jpeg.JPEGEncodeParam;import java.util.ArrayList;
import java.util.List;
import java.util.Stack;/*** @author: guorui fu* @versiion: 1.0* 逆波兰计算器 运算后缀表达式* 普通的运算字符串是中缀表达式* 中缀表达式转为后缀表达式： 按运算顺序将排序字符串变为后缀表达式* 中缀表达式转后缀表达式：其顺序是已经规定好的 大致是两个栈，* 遍历到符号是优先的压入数字栈，括号内的先从符号栈压入数字栈*/
public class PolandNoation {public static void main(String[] args) {//中缀表达式转成后缀表达式//1.先将字符串转成中缀表达式的listString expression = "1.1+((2+3)*4)-5.2";List infixExpressionList = toInfixExpressionList(expression);System.out.println("中缀表达式" + infixExpressionList );//2.将得到的中缀转为后缀List suffixExpressionList = parseSuffixExpressionList(infixExpressionList);System.out.println("后缀表达式对应的list=" + suffixExpressionList);double res = calculate(suffixExpressionList);System.out.println("运算结果=" + res);//        //定义一个后缀表达式
//        //为了方便，数字和符号使用空格隔开
//        String suffixExpression = "3 4 + 5 * 16 - ";
//        //先将"3 4 + 5 * 6 - " 放入Arraylist
//        //传递给一个方法，遍历list配合栈完成计算
//
//        List rpnList = getListString(suffixExpression);
//        System.out.println("rpnList=" + rpnList);
//        int res = calculate(rpnList);
//        System.out.println("运算结果=" + res);}//中缀转为后缀public static List parseSuffixExpressionList(List ls){//定义两个栈Stack s1 = new Stack();//符号栈//s2没有pop操作，还要逆序操作，因此不用栈，使用list
//        Stack s2 = new Stack();//存储中间结果List s2 = new ArrayList<>();//遍历lsfor (String item : ls) {//如果是数就入s2if (item.matches("\\d+(\\.\\d+)?")){s2.add(item);}else if (item.equals("(")){s1.push(item);}else if (item.equals(")")){//右括号while(!s1.peek().equals("(")){s2.add(s1.pop());}s1.pop();//弹出 (  消除小括号}else {//当item的优先级小于等于栈顶的优先级 将s1栈顶的运算符弹出加入s2中//有一个比较优先级高低的方法while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)){s2.add(s1.pop());}//还需要将item压入栈中s1.push(item);}}//将是s1中剩余的运算符依次加入到s2while (s1.size() != 0){s2.add(s1.pop());}return s2;//存放在list中，按顺序输出就是对应的后缀表达式对应的list}//中缀表达式转成对应的listpublic static List toInfixExpressionList(String s){//定义一个List ,存放中缀表达式List ls = new ArrayList<>();int i = 0;//是一个指针，用于遍历中缀表达式字符串String str;//多位数拼接char c;//遍历到的字符，放入cdo {//如果c是一个非数字，就需要加入到lsif ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57 && !".".equals(String.valueOf(s.charAt(i)))){ls.add("" + c);i++;}else {//如果是一个数，需要考虑多位数问题str = "";//str置成空串while (i < s.length() && ((c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57 || ".".equals(String.valueOf(s.charAt(i))))){str += c;i++;}ls.add(str);}}while (i < s.length());return ls;}//将一个逆波兰表达式放入Arraylistpublic static List getListString(String suffixExpression){//将suffixExpression分割 按空格String[] split = suffixExpression.split(" ");List list = new ArrayList<>();for (String e : split) {list.add(e);}return list;}//完成逆波兰表达式的运算public static double calculate(List ls){//1.创建一个栈Stack stack = new Stack<>();//遍历lsfor (String item : ls) {//使用正则表达式取出数if (item.matches("\\d+(\\.\\d+)?")){//入栈stack.push(item);}else{//pop出两个数并运算，在入栈double num2 = Double.parseDouble(stack.pop());double num1 = Double.parseDouble(stack.pop());double 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);}}//最后留在栈里的就是运算结果return Double.parseDouble(stack.pop());}
}//编写一个类 比较优先级高低的方法 返回优先级
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;}
}