逆波兰式的java实现与计算
逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）。
定义
一个表达式E的后缀形式可以如下定义：
（1）如果E是一个变量或常量，则E的后缀式是E本身。
（2）如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1'E2' op，这里E1'和E2'分别为E1和E2的后缀式。
（3)如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。
如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+
(a+b)*c-(a+b)/e的后缀表达式为：
(a+b)*c-(a+b)/e<br/>
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-
算法实现
将一个普通的中序表达式转换为逆波兰表达式的一般算法是：
首先需要分配2个栈，一个作为临时存储运算符的栈S1（含一个结束符号），一个作为输入逆波兰式的栈S2（空栈），S1栈可先放入优先级最低的运算符#，注意，中缀式应以此最低优先级的运算符结束。可指定其他字符，不一定非#不可。从中缀式的左端开始取字符，逐序进行如下步骤：
- 若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入S2栈
- 若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符优先级(不包括括号运算符)大于S1栈栈顶运算符优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符低于（不包括等于）该运算符优先级，最后将该运算符送入S1栈。
- 若取出的字符是“（”，则直接送入S1栈顶。
- 若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
- 重复上面的1~4步，直至处理完所有的输入字符
- 若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入S2栈。
完成以上步骤，S2栈便为逆波兰式输出结果。不过S2应做一下逆序处理。便可以按照逆波兰式的计算方法计算了！
计算方式
新建一个栈，如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。
代码实现
import java.util.*;
/**
* 逆波兰式生成
*/
public class RPN {
public static void main(String[] args) {
RPN("(${var1}+${var2})*1000/${var3} ");
RPN("(a+b)*c-(a+b)/e ");
System.out.println(compute(RPN("100/10")));
}
static Set<String> operator = new HashSet<String>() {{
add("+");
add("-");
add("*");
add("/");
}};
static Map<String, Integer> operatorLevelMap = new HashMap<String, Integer>() {{
put("+", 0);
put("-", 0);
put("*", 1);
put("/", 1);
}};
static Set<String> brackets = new HashSet<String>() {{
add("(");
add(")");
}};
static String bracketLeft = "(";
static String bracketRight = ")";
static String opType = "$";
static String opStart = "{";
static String opStop = "}";
static String space = " ";
public static Double compute(LinkedList<String> s1) {
LinkedList<Double> stack = new LinkedList<Double>();
while (s1.size() != 0) {
String tmp = s1.pop();
if (operator.contains(tmp)) {
Double d2 = stack.pop();
Double d1 = stack.pop();
Double r = doCompute(d1, d2, tmp);
stack.push(r);
} else {
stack.push(Double.valueOf(tmp));
}
}
return stack.pop();
}
private static Double doCompute(Double d1, Double d2, String operator) {
switch (operator) {
case "+":
return d1 + d2;
case "-":
return d1 - d2;
case "*":
return d1 * d2;
case "/":
return d1 / d2;
default:
throw new RuntimeException("操作符异常" + operator);
}
}
/**
* 生成逆波兰式
*/
public static LinkedList<String> RPN(String str) {
StringHolder holder = new StringHolder(str);
// 临时存储运算符
LinkedList<String> s1 = new LinkedList<String>();
// 输入逆波兰式
LinkedList<String> s2 = new LinkedList<String>();
while (!holder.finished()) {
// 5. 重复以下的1~4步，直至处理完所有的输入字符
String tmp = holder.next();
while (space.equals(tmp)) {
tmp = holder.next();
}
if (tmp == null) {
break;
}
if (!operator.contains(tmp) && !brackets.contains(tmp)) {
// 1. 若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入S2栈
s2.push(getOp(holder));
} else if (operator.contains(tmp)) {
// 2. 若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较
Integer operatorLevel = operatorLevelMap.get(tmp);
String s1Top = s1.peekFirst();
Integer s1TopLevel = operatorLevelMap.get(s1Top);
if (s1.size() == 0 || bracketLeft.equals(s1Top) || (operatorLevel - s1TopLevel) > 0) {
// 2.1 如果该运算符优先级(不包括括号运算符)大于S1栈栈顶运算符优先级，则将该运算符进S1栈
s1.push(tmp);
} else {
// 2.2.1 否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符低于（不包括等于）该运算符优先级
while (s1.size() != 0 && !bracketLeft.equals(s1Top) && (operatorLevel - s1TopLevel) <= 0) {
s2.push(s1.pop());
s1Top = s1.peekFirst();
s1TopLevel = operatorLevelMap.get(s1Top);
}
// 2.2.2 最后将该运算符送入S1栈。
s1.push(tmp);
}
} else if (bracketLeft.equals(tmp)) {
// 3. 若取出的字符是“（”，则直接送入S1栈顶。
s1.push(tmp);
} else if (bracketRight.equals(tmp)) {
// 4. 若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
while (s1.size() != 0 && !bracketLeft.equals(s1.peekFirst())) {
s2.push(s1.pop());
}
}
}
// 6. 将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入S2栈。
while (s1.size() != 0) {
if (s1.peekFirst().equals(bracketLeft)) {
s1.pop();
} else {
s2.push(s1.pop());
}
}
Collections.reverse(s2);
System.out.println(String.join(",", s2));
return s2;
}
/**
* 获取操作数
*/
public static String getOp(StringHolder holder) {
if (opType.equals(holder.current())) {
// 变量 除非遇到结束符，否则不结束
StringBuilder builder = new StringBuilder(opType);
// 如果字符未结束，并且下一个字符不是变量结束符。就添加下一个字符
while (!holder.finished() && !opStop.equals(holder.next())) {
builder.append(holder.current());
}
if (!opStop.equals(holder.current())) {
throw new RuntimeException(String.format("变量%s有误", builder.toString()));
}
builder.append(opStop);
return builder.toString();
} else {
// 常量
StringBuilder builder = new StringBuilder(holder.current());
while (!holder.finished()) {
if (!constantEnd(holder.next())) {
builder.append(holder.current());
} else {
holder.back();
break;
}
}
return builder.toString();
}
}
public static String constant = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890._";
public static boolean constantEnd(String tmp) {
if (space.equals(tmp) || operator.contains(tmp) || brackets.contains(tmp)) {
// 空格 操作符 括号
return true;
}
if (!constant.contains(tmp)) {
// 常规字符
return true;
}
return false;
}
public static class StringHolder {
private String str;
private int pos;
private String tmp;
public StringHolder(String str) {
this.str = str;
this.pos = -1;
}
public String next() {
if (pos + 1 == str.length()) {
this.tmp = null;
} else {
pos++;
this.tmp = String.valueOf(str.charAt(pos));
}
return this.tmp;
}
public void back() {
this.pos--;
this.tmp = String.valueOf(str.charAt(pos));
}
public String current() {
return tmp;
}
public boolean finished() {
return pos + 1 == str.length();
}
}
}