今天是很闷热的一天，还是坚持着学完既定课程并做好总结
关于中缀与后缀表达式
所述的 中缀表达式就是人们平时所看到的数学表达式形式，以人们易读的形式展现（数字之间夹杂着运算符）并且要考虑括号的优先计算。
这样的表达式其实是不利于计算机计算的，关于中缀表达式的计算机计算实现可以看我上一篇博客
伟大的计算机学者发明出一种后缀表达式，使计算机更容易计算数学式子，我们需要做的有两部分，第一部分是中缀转后缀表达，第二部分是后缀表达的计算
中缀转后缀表达
将中缀表达式转换为后缀表达式：
与转换为前缀表达式相似，遵循以下步骤：
(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
(2) 从左至右扫描中缀表达式；
(3) 遇到操作数时，将其压入S2；
(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
(4-1) 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
(4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
(5) 遇到括号时：
(5-1) 如果是左括号“(”，则直接压入S1；
(5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
(6) 重复步骤(2)至(5)，直到表达式的最右边；
(7) 将S1中剩余的运算符依次弹出并压入S2；
(8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。
举例一个中缀表达
1+((2+3)*4)-5
其转换为后缀的过程如下图所示
实际上这里并不需要两个栈结构，因为s2从始至终未执行pop出栈操作，且最后要对s2进行逆序排列，因此最方便的数据结构是使用list，顺序add顺序输出即可。
后缀表达的计算
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
例如后缀表达式“1 2 3 + 4 * + 5 -”：
(1) 从左至右扫描，将1和2和3压入堆栈；
(2) 遇到+运算符，因此弹出3和2（3为栈顶元素，2为次顶元素，注意与前缀表达式做比较），计算出3+2的值，得5，再将5入栈；
(3) 将4入栈；
(4) 接下来是×运算符，因此弹出4和5，计算出4×5=20，将20入栈；
(5) 接下来是+运算符，弹出20和1，计算20+1=21，将21入栈；
(6) 将5入栈；
(6) 最后是-运算符，计算出21-5的值，即16，由此得出最终结果。
程序实现
package com.tunan.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
//完成将中缀表达式转后缀表达式的操作
String expression = "1+((2+3)*4)-5";
List<String> infixExpressionList = toInfixExpressionList(expression);
System.out.println(infixExpressionList);
List<String> parseSuffixExpressionList = parseSuffixExpressionList(infixExpressionList);
System.out.println(parseSuffixExpressionList);
System.out.printf("expression %s = %d \n", expression, calculate(parseSuffixExpressionList));
}
//中缀list转后缀list
public static List<String> parseSuffixExpressionList(List<String> ls){
//定义两个栈
Stack<String> s1 = new Stack<String>();//符号栈
//储存中间结果的栈 不必是栈结构，可以用list，因为没有出栈操作
//Stack<String> s2 = new Stack<String>();
List<String> s2 = new ArrayList<String>();
//遍历ls
for (String item: ls){
//如果是数，直接加入到s2
if(item.matches("\\d+")){
s2.add(item);
} else if(item.equals("(")){
s1.push(item);
} else if(item.equals(")")){
//依次弹出s1的运算符加入到s2，直到遇到左括号为止，将这一对括号丢弃
while(!s1.peek().equals("(")){
s2.add(s1.pop());
}
s1.pop();//将左括号也弹出哦！！从而消除括号
} else{
//当item的优先级小于等于s1栈顶符号时，将s1栈顶运算符弹出加入到s2，再次比较
while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)){
s2.add(s1.pop());
}
//还需要将item压入栈
s1.push(item);
}
}
//将s1中 的依次弹出加入到s2
while(s1.size() != 0){
s2.add(s1.pop());
}
return s2;//s2 是list 因此按顺序输出即可，不需要像栈一样再进行倒序操作
}
//将中缀转成list
public static List<String> toInfixExpressionList(String s) {
List<String> ls = new ArrayList<String>();
int i = 0;//指针，用于遍历s
String str;//对多位数的拼接
char c;//遍历到的字符放入c中
do {
//如果c不是一个非数字
if((c = s.charAt(i)) < 48 ||(c = s.charAt(i)) > 57){
ls.add("" + c);
i++;
}else {//是数字就需要考虑多位数的拼接
str = "";//str置成空串
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;
}
//将逆波兰表达式，依次放到ArrayList中
public static List<String> getListString(String suffixExpression) {
//将suffixExpression分割
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<String>();
for(String ele: split){
list.add(ele);
}
return list;
}
//完成逆波兰表达式的计算
/*遇到 + 运算符，弹出4和3（4是栈顶元素，3是次栈顶元素），计算出3+4得7，将7入栈
将5入栈
下面遇到*运算符，因此弹出5和7，计算7*5得35，将35入栈
将6入栈
最后遇到 - 运算符，计算35-6，得最终结果*/
public static int calculate(List<String> ls){
//只需创建一个栈即可
Stack<String> stack = new Stack<String>();
//遍历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;
switch (item) {
case "+":
res = num1 + num2;
break;
case "-":
res = num1 - num2;
break;
case "*":
res = num1 * num2;
break;
case "/":
res = num1 / num2;
break;
default:
break;
}
stack.push(res + "");//int转string
}
}
//最后留在stack中的数是结果
return Integer.parseInt(stack.pop());
}
}
//编写一个返回运算符对应优先级的类
class Operation{
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 3;
public static int getValue(String operation){
int res = 0;
switch (operation) {
case "+":
res = ADD;
break;
case "-":
res = SUB;
break;
case "*":
res = MUL;
break;
case "/":
res = DIV;
break;
default:
System.out.println("运算符出错");
break;
}
return res;
}
}
程序结果是：
