什么是逆波兰表达式？
波兰表达式又叫做后缀表达式，是把运算量写在前面,把运算符写在后面。
中缀表达式如何转换为逆波兰表达式：
1、定义一个栈，用来存储操作数，在上一章节已经写了 https://www.jianshu.com/p/8e18d75c23a2 ；
2、从左到右遍历逆波兰表达式，得到每一个元素；
3、判断当前元素是运算符还是操作数；
4、如果是运算符，从栈中弹出两个操作数，完成运算，运算玩的结果再压入栈中；
5、操作数，把该操作数放入到栈中；
6、栈中最后一个元素，就是逆波兰表达式的结果，即是运算后的结果；
此思路借鉴了white code 的文章：https://blog.csdn.net/qq_43751200/article/details/104619611
逆波兰表达式计算代码如下：
public class StackCalculate {
public static int calculate(String[] expression)throws Throwable {
if (expression ==null) {
throw new Throwable("Expression is null");
}
if (expression.length ==0) {
return 0;
}
LinkStack stack =new LinkStack();
Integer pop1;
Integer pop2;
Integer result;
for (int i =0; i < expression.length; i++) {
switch (expression[i]) {
case "+":
pop1 = stack.pop();
pop2 = stack.pop();
result = pop1 + pop2;
stack.push(result);
break;
case "-":
pop1 = stack.pop();
pop2 = stack.pop();
//按照压栈和出栈的顺序，比如：压栈顺序为 17 5，那么5就在栈顶，17在栈底。
result = pop2 - pop1;//所以此处为pop2-pop1
stack.push(result);
break;
case "*":
pop1 = stack.pop();
pop2 = stack.pop();
result = pop1 * pop2;
stack.push(result);
break;
case "/":
pop1 = stack.pop();
pop2 = stack.pop();
//按照压栈和出栈的顺序，比如：压栈顺序为 17 5，那么5就在栈顶，17在栈底。
result = pop2 / pop1;//遇到除号，栈底的数除以栈顶的数
stack.push(result);
break;
default:
stack.push(Integer.valueOf(expression[i]));
}
}
return stack.pop();
}
}
LinkStack的代码如下：
/**
* 栈的特性：数据的插入和删除只能在栈顶操作
*
* @param <T>
*/
public class LinkStack {
public LinkStack(int size) {
this.size = size;
}
public LinkStack() {
this(DEFAULT_SIZE);
}
private Linktop;
private int size;
private static final int DEFAULT_SIZE =0;
/**
* 数据存储的节点
*/
class Link {
T data;
Linknext;
public Link(T data, Link next) {
this.data = data;
this.next = next;
}
}
/**
* 入栈操作
*
* @param data
*/
public void push(T data) {
Link head =top;
Link newTop =new Link(data, head);//这句已经表明指向了top，就没必要newTop.next = top
top = newTop;//是newTop成为栈顶
size++;
}
/**
* 出栈操作
*
* @return
*/
public T pop() {
if (top !=null) {
Link head =top;
top =top.next;
T t = head.data;
head =null;
size--;
return t;
}
return null;
}
/**
* 获取栈的长度
*
* @return
*/
public int getSize() {
return size;
}
/**
* 判断栈是否为空
*
* @return
*/
public boolean isEmpty() {
return size ==0;
}
@Override
public StringtoString() {
Link link =top;
for (int i =0; i
System.out.print(link.data +" ");
link = link.next;
}
System.out.println(" ");
return "LinkStack{" +
"top=" +top +
", size=" +size +
'}';
}
}
测试的运行结果如下：
再次感谢white code 所提供的的思路！https://blog.csdn.net/qq_43751200/article/details/104619611
