知道逆波兰表达式是一个偶然的情况，在用js的时候偶然发现了js中的一个eval函数，数学的表达式它竟然能直接解析出结果。后面通过查询才得知里面的核心是用的逆波兰表达式的算法。后面网上找了一下java的逆波兰表达式算法，没有找到，后面就干脆自己写一个，代码可能有点low希望大牛们可以指导一下。这里引出的逆波兰表达式通过java如何实现。代码：
import java.util.LinkedList;
import java.util.List;
public class ReversePolishNotation {
// 定义一个运算符堆栈character
private static LinkedList characterList = new LinkedList<>();
// 定义一个操作符堆栈operator
private static LinkedList operatorList = new LinkedList<>();
// 定义一个StringBuffer的可变字符串
private static StringBuffer sb = new StringBuffer();
// 定义一个解析表达式结果的集合
private static LinkedList resultList = new LinkedList<>();
/** 逆波兰表达式 以及表达式的运算*/
// 采用java语言对逆波兰表达式进行解析
public static void analysis(String str) {
// 将表达式字符串进行解析
String[] strArr = str.trim().split("");
String strRes = "";
// System.out.println(strArr[0]+"--"+strArr[1]+"--"+strArr[2]);
// 如果是数字就入栈 如果是其他的就对栈顶的进行运算，具体的步骤
// 显示入栈如果遇到运算符将栈顶的元素弹出进行运算得出的结果在入栈依次进行下去
// 如何解决运算符的优先级问题
// 根据元素进行操作
for (String s : strArr) {
if (s.equals("+") || s.equals("-")) {
operatorList.add(strRes.trim());
strRes = "";
// 表示是1级优先级 这个地方需要判断运算符堆栈的堆顶运算符的优先级比较
// 如果比堆顶的优先级高则直接入堆
// 如果比堆顶的优先级低则将堆顶的运算符加入到操作符堆中
// 在继续与下面的比较 如果还是小则重复上面的过程直到加入运算符堆中
priorityCompare(s);
} else if (s.equals("*") || s.equals("/")) {
operatorList.add(strRes.trim());
strRes = "";
priorityCompare(s);
} else if (s.equals("^") || s.equals("%")) {
operatorList.add(strRes.trim());
strRes = "";
priorityCompare(s);
} else if (s.equals("(")) {
operatorList.add(strRes.trim());
strRes = "";
characterList.add(s);
} else if (s.equals(")")) {
operatorList.add(strRes.trim());
strRes = "";
// 合并运算 一直到")"这个括号出现为止 将运算符的元素移动到操作符堆栈中
while (!characterList.peekLast().equals("(")) {
operatorList.add(characterList.pollLast());
}
characterList.removeLast();// 移除"("这个元素
} else {
// 表示是非运算符的处理
strRes = strRes + s;
}
}
if (strRes != "") {
operatorList.add(strRes);
strRes = "";
}
// 将operatorList里面的空元素剔除
while(operatorList.contains("")){
operatorList.remove("");
}
// 循环走过之后应该将运算符中的元素依次移除到操作符堆栈中
String strTmp = "";
while ((strTmp = characterList.pollLast()) != null) {
operatorList.add(strTmp);
}
analysisEquals(operatorList);
}
/** 运算符堆的优先级比较 */
public static void priorityCompare(String s) {
if (transformPriority(s) > transformPriority(characterList.peekLast())) {
// 表示优先级高 加入到运算符堆中
characterList.add(s);
} else {
// 将运算符堆的堆顶元素加入到操作符堆中并继续判断
String str = characterList.pollLast();
if (str != null) {
operatorList.add(str);
priorityCompare(s);
} else {
priorityCompare(s);
}
}
}
/** 优先级的转换 */
public static int transformPriority(String s) {
if (s != null) {
if (s.equals("+") || s.equals("-")) {
return 1;
} else if (s.equals("*") || s.equals("/")) {
return 2;
} else if (s.equals("^") || s.equals("%")) {
return 3;
} else if (s.equals("(")) {
return 0;
} else {
return 0;
}
}
return 0;
}
/** 解析组合式 */
public static void analysisEquals( LinkedList operatorList ) {
// 解析表达式的基本准则 如果遇到运算符就将运算符的前面两个元素和运算符弹出栈
for(String s : operatorList){
if(s.equals("+")||s.equals("-")||s.equals("*")
||s.equals("/")||s.equals("^")||s.equals("%")){
//将结果集的最后面的两个元素弹出并进行运算
Double d1 = Double.parseDouble(resultList.pollLast());
Double d2 = Double.parseDouble(resultList.pollLast());
resultList.add(operation(d2, d1, s).toString());
}else{
resultList.add(s);
}
}
// 将他们进行运算之后在加入中间然后在依次进行运算
System.out.println(resultList);
}
/**逆波兰表达式运算*/
public static Double operation(Double d1,Double d2,String s){
Double dou = 0.0;
switch(s){
case "+":
dou = d1+d2;
break;
case "-":
dou = d1-d2;
break;
case "*":
dou = d1*d2;
break;
case "/":
dou = d1/d2;
break;
case "^":
dou = Math.pow(d1, d2);
break;
case "%":
dou = d1%d2;
break;
}
return dou;
}
public static void main(String[] args) {
// String str = "a+b-(b-d)*e";//=> a,b,b,d,-,e,*,-,+
String str = "(100+(11-(90-18))*5)*0+205%5*0+2*22+((12-3)*5)*0";;
analysis(str);
// 打印一下操作符集合
System.out.println(operatorList);
}
}
网友评论