10
逆波兰式的java实现与计算
source link: http://blog.gavinzh.com/2020/03/20/Reverse-Polish-notation-Implement-with-java/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
逆波兰式（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)
)((a+b)e/)- c-(a+b)/e
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();
}
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK