Java数据结构与算法-栈（逆波兰表达式）原理及代码实现
1. 逆波兰表达式的介绍
2. 中缀转后缀的原因
3. 存储特点和原理
4. 栈实现中缀转后缀的思路
5. 代码实现
6. 注意事项
一，逆波兰表达式的介绍
前缀：
前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6
中缀：不再多说。
后缀：
逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后，例如： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
二，中缀转后缀
为什么要中缀转后缀呢？WHY?我中缀表达式看的多爽为啥要转换？但是呢计算机看中缀的话就比较麻烦，相反计算机更容易用后缀表达式进行计算，因此开发中我们需要将中缀表达式转换为后缀表达式。
三，后缀的特点及原理
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
四，转换思路
案例：逆波兰计算器
思路：
创建两个栈，一个为数栈，一个符号栈。 然后对进来的字符进行判断，如果是数字就直接进入数栈，如果是符号，当符号栈为空的时候直接入栈，然后继续扫描，当符号的优先级别小于等于符号栈顶的元素的运算级别的时候 也即是：operstack.peek()>=oper当前符号优先级时，就把符号栈顶出栈并且push到数栈中。 假如是（则直接进入operstack，然后接着执行第二步，如果是），则while循环依次operstack出栈，并且进入到数栈，然后再把（也移出operstack。 最后再把operstack里剩下的运算符，依次取出放到numstack中。逆序打印就是后缀表达式。具体实现步骤：
1)初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2)从左至右扫描中缀表达式；
3)遇到操作数时，将其压s2；
4)遇到运算符时，比较其与s1栈顶运算符的优先级：
1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
2.否则，若优先级比栈顶运算符的高，也将运算符压入s1；
3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
5)遇到括号时：(1)如果是左括号“(”，则直接压入s1(2)如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃6)重复步骤2至5，直到表达式的最右边7)将s1中剩余的运算符依次弹出并压入s28)依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
五，代码实现
package com.atxiaopeng.stack;
import java.util.List;
import java.util.Stack;
import java.util.ArrayList;
//中序表达式转后序表达式并且计算
public class Calculate {
public static void main(String[] args) {
// TODO Auto-generated method stub
//中缀：4 * 3 + 5 - 1
//4 3 * 5 + 1 -
//2.因为直接对str进行操作，不方便，因此先将"1+((2+3)×4)-5"=》中缀的表达式对应的List
String s = "4*(3+5)-1";
List ls1 =zhongXU(s);
List lst = houXU(ls1);
int res = cal(lst);
//Double.parseDouble(s)
System.out.println("中缀表达式："+ls1);
System.out.println("后缀表达式："+lst);
System.out.println("表达式结果为："+res);
}
//字符串转成中缀表达式集合。
public static List zhongXU(String s) {
List ls= new ArrayList();
int i = 0;
String str = "";
char c ;
do {
if ((c = s.charAt(i))57) {
ls.add(c+"");
i++;
} else {
str="";
while (i=48 &&(c=s.charAt(i))<=57) {
str+=c;
i++;
}
ls.add(str);
}
} while (i<s.length());
return ls;
}
//中缀转后缀表达式
public static List houXU(List ls) {
Stack stack = new Stack();
List ls2 = new ArrayList();
for (String item : ls) {
if (item.matches("\\d+")) {
ls2.add(item);
}else if (item.equals("(")) {
stack.push(item);
}else if (item.equals(")")) {
while(!stack.peek().equals("(")){
ls2.add(stack.pop());
}
stack.pop();
}else {
if (stack.size()!=0&&opers(stack.peek())>=opers(item)) {
ls2.add(stack.pop());
}
stack.push(item);
}
}
while (stack.size()!=0) {
ls2.add(stack.pop());
}
return ls2;
}
//比较符号的优先级
public static int opers(String s) {
int value = 0;
switch (s) {
case "+":
value = 1;
break;
case "-":
value = 1;
break;
case "*":
value = 2;
break;
case "/":
value = 2;
break;
default:
break;
}
return value;
}
//计算结果
public static int cal(List ls) {
int res = 0;
int num1 = 0;
int num2 = 0;
Stack st1 = new Stack();
for (String item : ls) {
if (item.matches("\\d+")) {
st1.push(item);
}else {
num2 = Integer.parseInt(st1.pop());
num1 = Integer.parseInt(st1.pop());
res = jiSuan(num1, num2, item);
st1.push(res+"");//最后栈里面有一个元素就是结果
}
}
return res;
}
//计算的方法
public static int jiSuan(int num1,int num2,String oper) {
int res = 0;
switch (oper) {
case "+":
res = num1+num2;
break;
case "-":
res = num1-num2;
break;
case "*":
res = num1*num2;
break;
case "/":
res = num1/num2;
break;
default:
break;
}
return res;
}
}
六，注意事项
以上程序不包括浮点数的运算，只针对与整型数字运算，完整的程序请看我下一篇。
作者：@大美妞
