题目：
一个对于一个单行的逆波兰表达式，由如下元素构成：
数字：十进制数字字符构成的正整数，比如 223
运算符：支持三种运算符^+和*，分别代表自增，加法和乘法
分隔符：一个或者多个空格
例如下面的字符串就是个逆波兰表达式
2 3 4 * ^ 5 +
逆波兰表达式在一个基于栈的虚拟机中求解，虚拟机的栈能保存16个整数，虚拟机从左向右扫描表达式，遇到整数就压栈，遇到表达式则从栈顶弹出若干个整数进行计算，计算结果重新压回栈中。
其中运算符^从栈顶弹出一个整数，增加1之后压栈；运算符+和*从栈顶弹出两个整数，分别做相加和相乘运算后压栈。如果遇到运算符的时候，栈内没有足够的整数，称为下溢出，返回-1；
把整数压栈的时候，如果栈没有足够的空间，称为上溢出，返回-2；如果整个计算过程中没有发生溢出，在整个表达式求解完成后，返回栈顶的整数。
说明：该题来自2017阿里巴巴实习笔试编程题，答案是自己写的，如有错误，敬请指正！
public class AlibabaTest {
public static void main(String[] args) {
ArrayList<Integer> inputs = new ArrayList<Integer>();
Scanner in = new Scanner(System.in);
String line = in.nextLine();
if(line != null && !line.isEmpty()) {
int res = resolve(line.trim());
System.out.println(String.valueOf(res));
}
}
// write your code here
public static int resolve(String expr) {
// 获取字符串集合
StringTokenizer st = new StringTokenizer(expr);
// 创建栈来存储操作数
LinkedListStack<Integer> stack = new LinkedListStack<Integer>();
// 遍历字符串集合
while (st.hasMoreTokens()) {
// 获取一个字符串
String str = st.nextToken();
switch (str) {
case "*":
// 双目操作需要保证数据栈至少有两个操作数
if (stack.size() >= 2) {
int oper1 = stack.pop();
int oper2 = stack.pop();
stack.push(oper1 * oper2);
} else {
// 栈内没有足够的整数，称为下溢出，返回-1
return -1;
}
break;
case "+":
// 双目操作需要保证数据栈至少有两个操作数
if (stack.size() >= 2) {
int oper1 = stack.pop();
int oper2 = stack.pop();
stack.push(oper1 + oper2);
} else {
// 栈内没有足够的整数，称为下溢出，返回-1
return -1;
}
break;
case "^":
if (!stack.isEmpty()) {
int oper = stack.pop();
oper += 1;
stack.push(oper);
} else {
// 栈内没有足够的整数，称为下溢出，返回-1
return -1;
}
break;
default:
// 如果是操作数，直接入栈
stack.push(Integer.valueOf(str));
break;
}
}
// 返回栈顶元素
return stack.pop();
}
}
题目：如何用栈只扫描一次就能计算中缀表达式的值？
思路：
1.创建一个空的操作数栈
2.创建一个空的操作符栈
3.遍历每一个字符，并根据情况处理
如果是数字则直接压入操作数栈
如果是操作符则判断优先级，并进行处理
如果是"("直接压入操作符栈
如果是")"，则从操作符栈中弹出运算符，直到"("出栈；但"("不输出
4.要保证操作数栈和操作符栈为空
/**
* 计算中缀表达式结果
* @param infix 中缀表达式
* @return 运算结果
*/
public static int resultOfInfix(String infix) {
// 1.获取字符串集合
StringTokenizer st = new StringTokenizer(infix);
// 2.1 创建栈来存储操作数
LinkedListStack<Integer> datas = new LinkedListStack<Integer>();
// 2.2 创建栈来存储操作符
LinkedListStack<String> opers = new LinkedListStack<String>();
// 标记运算符优先级
boolean priority = false;
// 3.遍历字符串集合
while (st.hasMoreTokens()) {
// 3.1 获取下一个字符串
String str = st.nextToken();
boolean flag = false;
// 3.2 检查字符串
switch (str) {
case "(":
case "+":
case "-":
case "*":
case "/":
break;
// 遇到")"时，从栈中弹出运算符，直到"("出栈；但"("不输出
case ")":
while (!opers.top().equals("(")) {
calculate(datas, opers);
}
// 将"("弹出
opers.pop();
flag = true;
break;
default:
// 如果是操作数则压入数据栈
datas.push(Integer.valueOf(str));
flag = true;
break;
}
// 3.3 如果对")"和操作数做过处理，则结束当前循环，继续读取下一个字符串
if (flag) {
continue;
}
// 3.4 操作符栈不为空，则判断运算符优先级
if (!opers.isEmpty()) {
priority = compare(opers.top().toCharArray()[0], str.toCharArray()[0]);
// 栈内运算符优先级高
if (priority) {
calculate(datas, opers);
}
}
// 3.5 运算符入栈
opers.push(str);
}
// 4.操作符栈不为空，说明存在数据未处理
while (!opers.isEmpty()) {
calculate(datas, opers);
}
// 5.返回运算结果
return datas.pop();
}
/**
* 运算
* @param datas 数据栈
* @param opers 操作符栈
*/
public static void calculate(LinkedListStack<Integer> datas, LinkedListStack<String> opers) {
int oper1 = datas.pop();
int oper2 = datas.pop();
switch (opers.pop()) {
case "*":
datas.push(oper2 * oper1);
break;
case "/":
datas.push(oper2 / oper1);
break;
case "+":
datas.push(oper2 + oper1);
break;
case "-":
datas.push(oper2 - oper1);
break;
default:
break;
}
}
测试代码如下：
public static void main(String[] args) {
System.out.println("--------------------");
String string = "( 1 + 2 ) * ( 5 - 3 )";
int result = resultOfInfix(string);
// 结果为6
System.out.println(result);
}