package datastructure.stack;
import java.util.*;
/**
* <h3>netty_lecture</h3>
* <p>逆波兰计算器</p>
* 1+((2+3)*4)-5 ==> 1 2 3 + 4 * + 5 1
* @author : myron
* @date : 2020-03-18 23:48
**/
public class PolandNotation {
private static final int MINAS = 0;
private static final int PLUS = 0;
private static final int MULTI = 1;
private static final int DIV = 1;
public static void main(String[] args){
String expression = "1,+,(,(,200,+,3,),*,9,),-,5";
List<String> list = middleExpressionToList(expression);
List<String> suffixExp = middleExpToSuffixExp(list);
System.out.println("中缀表达式:"+ list);
System.out.println("后缀表达式:" + suffixExp);
int result = calculate(suffixExp);
System.out.println("结果为:" + result);
}
/**
* 中缀表达式转List
* @param expression
* @return
*/
public static List<String> middleExpressionToList(String expression){
String[] split = expression.split(",");
List<String> list = Arrays.asList(split);
return list;
}
/**
* 中缀表达式转后缀表达式list
* @param middleExpList
* @return
*/
public static List<String> middleExpToSuffixExp(List<String> middleExpList){
Stack<String> s1 = new Stack<>();
List<String> s2 = new ArrayList<>();
for (String oper:middleExpList){
int priority = getPriority(oper);
if(oper.matches("\d+")){
s2.add(oper);
}else if("(".equals(oper)) {
s1.push(oper);
} else if(")".equals(oper)){
while(!"(".equals(s1.peek())){
s2.add(s1.pop());
}
s1.pop();
}else{
while(s1.size() != 0 && priority <= getPriority(s1.peek())){
s2.add(s1.pop());
}
s1.push(oper);
}
}
while(s1.size() != 0){
s2.add(s1.pop());
}
return s2;
}
/**
* 计算方法
* @param list :后缀表达式
* @return
*/
public static int calculate(List<String>list){
//创建栈
Stack<String> stack = new Stack<>();
//遍历表达式list
for(String str: list){
/**正则匹配,是数字,入栈*/
if(str.matches("\d+")){
stack.push(str);
/**运算符,则弹出两位数,进行运算*/
}else{
int num1 = Integer.parseInt(stack.pop());
int num2 = Integer.parseInt(stack.pop());
int result = 0;
if(str.equals("+")){
result = num1 + num2;
}else if(str.equals("-")){
result = num2 - num1;
}else if(str.equals("*")){
result = num1 * num2;
}else if(str.equals("/")){
result = num2/num1;
}else{
throw new RuntimeException("不支持该符号!");
}
//预算结果入栈
stack.push(result + "");
}
}
//返回运算结果
return Integer.parseInt(stack.pop());
}
/**
* 获取符号的优先级
*/
public static int getPriority(String oper){
if (oper.equals("+")) {
return PLUS;
}else if(oper.equals("-")){
return MINAS;
}else if(oper.equals("*")){
return MULTI;
}else if(oper.equals("/")){
return DIV;
}
return -1;
}
}