思路
数字输出，运算符进栈，括号匹配出栈，栈顶优先级出栈
a、首先使用两个栈 一个是s1 一个是s2 s1 是用来临时存储运算符的， s2 是用来存放输入的逆波兰表达式的，
b、从中缀表达式的最左端开始，逐个读取每一个字符，如果操作数，则压入s2，如果是左括号，则压入s1，如果为右括号，则将s1中的运算符依次取出并且压入s2，直到遇到左括号，但是该左括号出栈 但不压入s2，如果为操作符， 判断s1是否为空，如果为空 则将它压入s2，如果扫描到的比栈顶的元素的优先级大 将它入栈，如果扫描到的比小于栈顶或者等于栈顶的优先级小，直到扫描到的元素大于栈顶的元素（注意这里是一个循环），然后判断s1里面如果还有运算符 则一一出栈压入到s2中
c、然后这个时候所有的数据全部在s2中，这个时候从的将s2逆置，从栈底开始取元素，开始扫描，如果扫描到的是一个运算符，则将他之前扫描到的两个元素做运算，得到存储到该位置，一直扫描，直到栈里还剩一个元素，就得到结果。
代码实现
自己写的 就是为了实现可能还有问题 大家可以提出来
public class ReversePolishUtil {
/**
*是一个中缀表达式
* @param express
*/
public static void Reverse(String[] express) {
if (express == null || express.length == 0) {
抛出异常;
}
运来存放运算符
StackDemo</a> s1 = new StackDemo ();
用来存放输入逆波兰表达式
StackDemo s2 = new StackDemo ();
依次遍历这个数组
for (int i = 0; i < express.length; i++) {
String nowChar = express[i];
Pattern pattern = Pattern.compile("[0-9]*");
boolean isMacth = pattern.matcher(nowChar).matches();
if (isMacth) {
如果是数字 直接压入s2
s2.push(nowChar);
} else {
否则就是操作符 就得判断s1 栈顶的元素
if (s1.empty()) {
如果为空 直接push
s1.push(nowChar);
} else if (nowChar.equals("(")) {
如果是左括号 直接push s1
s1.push(nowChar);
} else if (nowChar.equals(")")) {
如果是右括号， s1中的运算符依次出栈 压入到s2中， 直到遇到左括号， 但是左括号是直接出栈的
while (!s1.empty() && !s1.peek().equals("(")) {
s2.push(s1.pop());
}
然后将左括号也给出栈
s1.pop();
} else if (nowChar.equals("+") || nowChar.equals("-")) {
1、如果扫描到的比栈顶的元素的优先级大 将它入栈
2、如果扫描到的比小于栈顶或者等于栈顶的优先级小，知道扫描到的元素大于栈顶的元素扫描到的运算符
while (!s1.empty() && !s1.peek().equals("(")) {
在这里只要不遇到左括号 就一直出栈，因为优先级都比它大
s2.push(s1.pop());
}
在这里是要么遇到括号 要么s1出栈为null了
s1.push(nowChar);
} else if (nowChar.equals("*") || nowChar.equals("/")) {
在这里一直出栈的情况是只有当遇到 * 和/
while (!s1.empty() && s1.peek().equals("*") || s1.peek().equals("?")) {
s2.push(s1.pop());//出栈
}
s1.push(nowChar);
}
}
如果s1里面还有操作符 则push到s2里面
while (!s1.empty()) {
s2.push(s1.pop());
}
while (!s2.empty()) {
Log.e("Reverse", s2.pop() + "");
}
}
}
然后使用数组手写一个栈，上面的逆波兰就用的这个demo
public class StackDemo {
//初始数组的大小
private int capacity = 3;
//数组中元素的个数
private int size = 0;
//由于是数组设计到扩容 ，这里直接是扩容1.5倍
private int increment = 2;
private Object[] elementData = new Object[capacity];
public StackDemo() {
}
public StackDemo(int capacity) {
this.capacity = capacity;
}
//实现一个push的方法
public void push(Object obj) {
//在这里要判断是否超出了 如果超过了就得扩容 注意相等也要判断 坑了
if (size >= elementData.length) {
grow(); //扩容
}
elementData[size] = obj;
size++;
}
//移除栈顶的元素
public Object pop() {
if (elementData == null || elementData.length == 0 || size == 0) {
return "";
}
size--;
return elementData[size];
}
public boolean empty() {
if (elementData == null || elementData.length == 0 || size == 0) {
return true;
}
return false;
}
/**
* 查看栈顶元素但是不删除
* @return
*/
public Object peek() {
if (elementData == null || elementData.length == 0 || size == 0) {
return "";
}
return elementData[size - 1];
}
//数组大小的扩容
private void grow() {
int newcapacity = (increment * elementData.length);
elementData = Arrays.copyOf(elementData, newcapacity);
}
}
最后调用：
String[] string = {"12", "+", "4", "+", "5","*","(","3","-","2",")"};
ReversePolishUtil.Reverse(string); 吧上一篇文章的结果打印出来是没问题的
