逆波兰表达式、波兰表达式
1.前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。比如:- × + 3 4 5 6
2.中缀表达式就是常见的运算表达式，如(3+4)×5-6
3.后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后,比如:3 4 + 5 × 6
一.通过逆波兰表达式计算结果
我们先看一个例子...后缀表达式3 4 + 5 × 6 -的计算
1.从左至右扫描，将3和4压入堆栈；
2.遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；
3.将5入栈；
4.接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
5.将6入栈；
6.最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
/**
* 通过逆波兰表达式计算结果
* @param ls
* @return
*/
//求逆波兰表达式的值
public static int calcRevPolishNotation(String express){
Stack<String> stack = new Stack<>();
for (int i = 0; i <express.length() ;i++) {
// 普通数值的处理
if ((express.charAt(i) + "").matches("\\d")){
stack.push(express.charAt(i) + "");
// + - * / 运算符的处理
}else if ((express.charAt(i) + "").matches("[\\+\\-\\*\\/]")){
String k1 = stack.pop();
String k2 = stack.pop();
// 计算结果
int res = calcValue(k1, k2, (express.charAt(i) + ""));
stack.push(res+"");
}
}
return Integer.valueOf(stack.pop());
}
//根据运算符计算结果
private static int calcValue(String k1, String k2, String c) {
switch(c){
case "+":
return Integer.valueOf(k1)+Integer.valueOf(k2);
case "-":
return Integer.valueOf(k2)-Integer.valueOf(k1);
case "*":
return Integer.valueOf(k1)*Integer.valueOf(k2);
case "/":
return Integer.valueOf(k2)/Integer.valueOf(k1);
default:
throw new RuntimeException("没有该类型的运算符！");
}
}
二.中缀表达式转换为后缀表达式（逆波兰表达式）
中缀表达式转后缀表达式主要用到了栈进行运算符处理，队列进行排序输出，规则为：
1.数字直接入队列
2.运算符要与栈顶元素比较
①栈为空直接入栈
②运算符优先级大于栈顶元素优先级则直接入栈
③小于或等于则出栈入列，再与栈顶元素进行比较，直到运算符优先级小于栈顶元
素优先级后，操作符再入栈
3.操作符是 ( 则无条件入栈
4.操作符为 )，则依次出栈入列，直到匹配到第一个(为止，此操作符直接舍弃，(直接出栈舍弃
/**
* 将中缀表达式转换为后缀表达式（逆波兰表达式）
* @param express
* @return
*/
public static String transfer(String express){
Stack<String> stack = new Stack<>();
List<String> list= new ArrayList<>();
for (int i=0;i<express.length();i++){
if ((express.charAt(i)+"").matches("\\d")){
list.add(express.charAt(i)+"");
}else if((express.charAt(i)+"").matches("[\\+\\-\\*\\/]")){
//如果stack为空
if (stack.isEmpty()){
stack.push(express.charAt(i)+"");
continue;
}
//不为空
//上一个元素不为（，且当前运算符优先级小于上一个元素则，将比这个运算符优先级大的元素全部加入到队列中
while (!stack.isEmpty()&&!stack.lastElement().equals("(")&&!comparePriority(express.charAt(i)+"",stack.lastElement())){
list.add(stack.pop());
}
stack.push(express.charAt(i)+"");
}else if(express.charAt(i)=='('){
//遇到左小括号无条件加入
stack.push(express.charAt(i) + "");
}else if(express.charAt(i)==')'){
//遇到右小括号，则寻找上一堆小括号，然后把中间的值全部放入队列中
while(!("(").equals(stack.lastElement())){
list.add(stack.pop());
}
//上述循环停止，这栈顶元素必为"("
stack.pop();
}
}
//将栈中剩余元素加入到队列中
while (!stack.isEmpty()){
list.add(stack.pop());
}
StringBuffer stringBuffer = new StringBuffer();
//变成字符串
for (String s : list) {
stringBuffer.append(s);
}
return stringBuffer.toString();
}
/**
* 比较运算符的优先级
* @param o1
* @param o2
* @return
*/
public static boolean comparePriority(String o1,String o2){
return getPriorityValue(o1)>getPriorityValue(o2);
}
/**
* 获得运算符的优先级
* @param str
* @return
*/
private static int getPriorityValue(String str) {
switch(str){
case "+":
return 1;
case "-":
return 1;
case "*":
return 2;
case "/":
return 2;
default:
throw new RuntimeException("没有该类型的运算符！");
}
}
京公网安备 11010502036488号