Java数据结构（逆波兰表达式）
最近在学习java数据结构的相关知识，记录一下学习的内容，算是每天的总结，今天学习的是栈相关的内容，然后学习前缀，中缀，后缀表达式，下面介绍一下，这三种表达式的含义

1. 中缀：中缀表达式，是我们最常见的表达式，就是日常算式，比如4+9-90*(5-1)，这种结构是人类能够了解并且计算的表达式但是计算机却不好理解
2. 后缀：后缀表达式，这里先不说后缀表达式是什么，先说怎么用，对于中缀表达式1+((2+3)*4)-5，它对应的后缀表达式是：[1, 2, 90, +, 8, *, +, 230, -]，在这里我们从左向右扫描后缀表达式，对于数字就入栈，如果遇到符号，就弹出两个元素进行计算，并将结果入栈，最后栈中的元素就是我们想要的运算结果，不相信可以演算：1,2,90，遇到+，进行运算：1，92，8，遇到乘号，进行运算：1，736，遇到加号开始运算：737，230，遇到减号，开始运算：507，也就是说，利用后缀表达式和栈，我们就可以利用计算机迭代轻易的求出表达式的解
3. 前缀表达式，也成为波兰表达式，对于波兰表达式，它同样具备和后缀表达式相同的功能，那就是表达式的求值，只不过他需要我们从右向左遍历手上的前缀表达式
   下面是前缀表达式的求值代码

public static int sovle(LinkedList<String> opt) {Stack<String> stack = new Stack<String>();for(String str:opt) {if(str.matches("\\d+")) {//如果是数字stack.add(str);}else {//如果是操作符String o1 = stack.pop();String o2 = stack.pop();Integer result = func(o1, o2, str);stack.push(result.toString());}}String num = stack.pop();return Integer.parseInt(num);}

但是我们的问题往往是，我们如何才能拿到后缀表达式呢，或者说，如何才能将日常的中缀表达式转化成后缀表达式呢，这就涉及到了今天学习的内容，为了便于理解，我们举一个不太恰当的例子，我们把后缀表达式的构建过程看成是梁山好汉的排座次的过程

我们将表达式中的符号进行简单的类比，数字就相当于平民英豪，运算符相当于当过官的英豪，而对于括号可能有点不同，因为括号不属于运算符，我们暂且归为官的一种，但是他们是有家室的官员，因为左右括号总是成对出现（这该死的爱情），下面介绍排位规则，一众英豪来到忠义堂前，按照市井次序排成一列，也就是我们最常见的中缀表达式，按照从左到右的次序一个个上前验明正身，对于平民英豪，因为其贫苦出身，直接进入忠义堂，依次落座

那么，1就做到第一把交椅，遇到第二个英豪，也就是加号，它属于当过官的英豪，未免有些规矩，他的规矩就是，他们做过官的要坐在一块，而且还要做领导层

所以就单独做了一块地，而且，根据做官的大小，他们也有尊卑之分，这体现到排位中就是，如果我的优先级小于等于我前面人的优先级，说明我的官衔大（一品大于二品，hhh原谅我在瞎编），我就会说：快滚出来，给小爷让个位置，这时前面的操作符出栈，然后无家可归（可怜），于是就去到隔壁，压入隔壁的栈中，但是此时我前面又会有一个人（如果栈没有空的话）,此时我还会重复我的操作，但是对于左括号妹妹，我也会温柔一些，会让她坐我前面，但是对于，右括号哥哥，他就比较暴躁（比普通运算符暴躁，对于左括号都是直接进栈，她不会检测前面坐的是谁，而对于右括号，他只允许他前面是左括号，于是就有了下面的样子

下一个入栈的是右括号，他会讲：我只要我的括号妹妹，你们都给我消失，所以前面的运算符们一个个出栈，去到隔壁，直到遇到左括号，左括号也出栈和右括号一块，远走高飞，于是我们看到了如下结果

最后市井英豪尽数入栈，但是分居不可取，乃将官府人员的栈顶元素，一次弹出，压入隔壁，组成的就是后缀表达式的前身

下面是从韩顺平老师那里copy的官方说法：众所周知，excel从来都只是一个画图工具
中缀转后缀
* 案例：1+((2+3)*4)-5
* 1. 对于拿到手的中缀表达式，我们要先建立两个栈s1，s2
* 2.从左向右扫描表达式，遇到数字就将其入栈s2
* 3.如果遇到的是操作符，就先比较其于s1栈顶操作符的优先级
* 3.1当然，有可能s1此时为空栈，我们就可以直接将操作符入栈
* 3.2或者如果运算符是(也直接入栈即可
* 3.3如果如果运算优先级高于 栈顶元素，则将运算符入栈
* 3.4否则，将s1中操作符弹出，压入到s2中，然后用新的栈顶元素
* 与之比较，重复步骤三
* 4. 如果是括号，对于左括号，直接入栈
* 如果遇到的是右括号，就直接将s1中的元素安抚弹出并压入s2,直到遇到左括号
* 最后将两个括号舍弃
* 5.将s1中剩余元素，弹出，压入s2
下面是代码实现：

package com.shunping.poland;import java.util.LinkedList;
import java.util.Stack;public class Poland {public static void main(String[] args) {// TODO Auto-generated method stub//拿到中缀表达式737-230String str = "1 + ( ( 2 + 90 ) * 8 ) - 230";//表达式打成list便于调用LinkedList<String> pol = strTolist(str);//进行逆波兰转换//System.out.println(pol.toString());LinkedList<String> opt = toPoland(pol);System.out.println("后缀："+opt.toString());System.out.println("运算结果："+sovle(opt));}public static LinkedList<String> strTolist(String str) {LinkedList<String> result = new LinkedList<String>();String[] strs = str.split(" ");for(String item:strs) {result.add(item);}return result;}public static LinkedList<String> toPoland(LinkedList<String> pol) {Stack<String> opt = new Stack<String>();LinkedList<String> num = new LinkedList<String>();for(String str:pol) {//如果扫描到数字就直接入栈numif(str.matches("\\d+")) {num.add(str);}else {//如果是运算符或者括号if(opt.isEmpty()||str.equals("(")) {//如果运算符栈为空，或者得到的是一个左括号，直接入栈opt.push(str);}else if(str.equals(")")) {//如果遇到右括号，就将opt中元素弹出并放入num，知道遇到左括号while(!opt.peek().equals("(")) {num.add(opt.pop());}//弹出左括号opt.pop();}else {//而且此时应该可以想到，栈内不存在一个配对的右括号//就算有，也应该在前面匹配过了，最多有一个左括号//此时str为运算符，而且此时，栈一定不为空while(true) {if(opt.isEmpty()) {opt.push(str);break;}else if(opt.peek().equals("(")||priority(str)>priority(opt.peek())) {//如果此时栈顶为左括号入栈//如果此时操作符大于栈顶元素，则入栈opt.push(str);break;}else {//此时运算符等级小于等于栈顶元素//opt栈顶元素压入numnum.add(opt.pop());//这里没有跳出循环//也就是说，当前操作符会接着和下一个栈顶元素比较}}}}}while(!opt.isEmpty()) {//将操作符压入numnum.add(opt.pop());}return num;}public static int priority(String opt) {if(opt.equals("+")||opt.equals("-")) {return 1;}else {return 2;}}public static int sovle(LinkedList<String> opt) {Stack<String> stack = new Stack<String>();for(String str:opt) {if(str.matches("\\d+")) {//如果是数字stack.add(str);}else {//如果是操作符String o1 = stack.pop();String o2 = stack.pop();Integer result = func(o1, o2, str);stack.push(result.toString());}}String num = stack.pop();return Integer.parseInt(num);}public static Integer func(String x, String y, String opt) {Integer xx = Integer.parseInt(x);Integer yy = Integer.parseInt(y);if(opt.equalsIgnoreCase("+")) {return xx+yy;}else if(opt.equalsIgnoreCase("-")) {return yy-xx;}else if(opt.equalsIgnoreCase("*")) {return xx*yy;}else if(opt.equalsIgnoreCase("/")) {return yy/xx;}else {return 0;}}
}