java利用逆波兰表达式（后序表达式）计算结果
1.前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。比如:- × + 3 4 5 6
2.中缀表达式就是常见的运算表达式，如(3+4)×5-6
3.后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后,比如:3 4 + 5 × 6 -
这里说一下大概实现的步骤：
- 初始化两个栈：运算符栈s1和储存中间结果的栈s2;
- 从左至右扫描中缀表达式；
- 遇到操作数（操作数就是数字）时，直接压入s2;
- 遇到运算符时，比较其与s1栈顶运算符的优先级：
1)如果s1为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈；
2)否则，做优先级比栈顶运算符的高，也将运算符压入s1；
3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到（4.1）与s1中新的栈顶运算符相比较 - 遇到括号时：
1)如果时左括号“（”，则直接压入s1
2)如果是右括号“）”，则一次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃 - 重复步骤2-5，直到表达式的最右边；
- 将s1中剩余的运算符一次弹出并压入s2；
- 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
代码实现的计算机在输入的字符串的时候是可以加小括号的。
具体的功能和流程,代码里的注释写的很清楚了:
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 利用逆波兰表达式（后序表达式）计算结果
*/
public class PolandNotation {
public static void main(String[] args) {
//将用户输入的字符串转化为 集合（ArrayList）类型的 方便后面栈的操作
// “(3+4)*5-2” --> “[(,3,+,4,),*,5,-,2]”
String s = "(3+4)*5-2";
//将字符串转化为集合
List<String> sl = toInfixExpressionList(s);
System.out.println("将字符串 转化为 集合类型后的结果为：" + sl);
//将集合转化为后缀表达式
List<String> s2 = parseSuffixExpreesionList(sl);
System.out.println("转化为后缀表达式的结果为：" + s2);
//计算后缀表达式的结果
int res=calculator(s2);
System.out.printf("最后的运算结果是：%d",res);
}
//将用户输入的字符串转化为 集合（ArrayList）类型的 方便后面栈的操作
// “（3+4）*5-2” --> “[（,3,+,4,）,*,5,-,2]”
public static List<String> toInfixExpressionList(String s) {
List<String> list = new ArrayList<String>();
int index = 0; //索引，相当于指向字符串每一个元素的指针
char c; //将字符串中取出的元素付给c
while (index < s.length()) {
//首先判断c是不是数字
if ((c = s.charAt(index)) < 48 || (c = s.charAt(index)) > 57) {
//如果不是数字 直接将其加入到集合里面
list.add("" + c);
index++;
} else {
//如果是数字的话，需要判断是不是多位数
//如果是多位数的话，将多位数转化为String
String num = "";
while (index < s.length() && (c = s.charAt(index)) >= 48 && (c = s.charAt(index)) <= 57) {
num += c;
index++;
}
list.add(num);
}
}
return list;
}
/**
* 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中剩余的运算符一次弹出并压入s2；
* 8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
*/
public static List<String> parseSuffixExpreesionList(List<String> ls) {
Stack<String> s1 = new Stack<String>();
List<String> s2 = new ArrayList<String>();
for (String item : ls) {
if (item.matches("\\d+")) {
s2.add(item);
}else if(s1.empty()){
s1.push(item);
} else if (item.equals("(")) {
s1.push(item);
} else if (item.equals(")")) {
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop();
} else if (Operation.getValue(s1.peek()) < Operation.getValue(item)) {
s1.push(item);
} else if (Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
do {
s2.add(s1.pop());
} while (!s1.empty()&&Operation.getValue(s1.peek()) >= Operation.getValue(item));
s1.push(item);
} else {
System.out.println("输入的字符有误");
}
}
for (String s:s1){
s2.add(s);
}
return s2;
}
//计算，算出 后缀表达式 的结果
public static int calculator(List<String> list) {
Stack<String> stack = new Stack<String>();
for (String item : list) {
if (item.matches("\\d+")) {
stack.push(item);
} else {
int num1 = Integer.parseInt(stack.pop());
int num2 = Integer.parseInt(stack.pop());
int res = 0;
if (item.equals("+")) {
res = num1 + num2;
} else if (item.equals("-")) {
res = num2 - num1;
} else if (item.equals("*")||item.equals("x")) {
res = num1 * num2;
} else if (item.equals("/")) {
res = num2 / num1;
} else {
throw new RuntimeException("输入的符号不正确");
}
stack.push("" + res);
}
}
return Integer.parseInt(stack.pop());
}
}
class Operation {
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;
public static int getValue(String s) {
if (s.equals("+")) {
return ADD;
} else if (s.equals("-")) {
return SUB;
} else if (s.equals("*")||s.equals("x")) {
return MUL;
} else if (s.equals("/")) {
return DIV;
}else if(s.equals("(")){
return 0;
} else{
System.out.println("没有该运算符！");
}
return 0;
}
}
