铭记:
源码下载
一、逆波兰表达式（后缀表达式）
(3+4)*5-6 对应的后缀表达式就是 3 4 + 5 * 6 -
1、逆波兰表达式计算规则
- 1、从左到右扫描，将 3 和 4 压入堆栈
- 2、遇到 + 运算符，因此弹出 4 和 3 ，计算出 3 + 4 = 7，在将 7 压入栈
- 3、将 5 入栈
- 4、接下来是 * 运算符，因此弹出 5 和 7，计算出 7 * 5 = 35，将 35 压栈
- 5、将 6 入栈
- 6、最后是 - 运算符，计算出 35 - 6 = 29，最后把 29 压入栈
2、中缀表达式 转换为 逆波兰表达式（后缀表达式）
后缀表达式：适合计算式进行运算，但是不适合人的书写；
中缀表达式：适合人的书写，但是不适合计算式运算；
所以需要把 [中缀表达式] 转为 [后缀表达式]
思路：
- 1、初始化两个栈：运算符栈（s1）和 存储中间结果的栈（s2）
- 2、从左到右扫描中缀表达式
- 3、遇到操作数时，将其压s2
- 4、遇到运算符时，与 s1 栈顶的运算符比较优先级
- 4.1、如果 s1 为空，或栈顶运算符为左括号"("，则直接将此运算符入栈
- 4.2、否则，若优先级比栈顶运算符的高，也将运算符压入s1
- 4.3、否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到 4.1 与 s1 中新的栈顶运算符相比较
- 5、遇到括号时
- 5.1、如果是左括号"("，则直接压入s1
- 5.2、如果是右括号")"，则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到左括号为止，此时将这一对括号丢弃
- 6、重复步骤 2~5，直到表达式的最右侧
- 7、将 s1 中剩余的运算符依次弹出并压入 s2
- 8、依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
二、代码 PolandNotation
package com.raven.alg.s4stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 逆波兰计算器
* <p>
* 例如：(3+4)*5-6 对应的后缀表达式就是 3 4 + 5 * 6 -
* 1、从左到右扫描，将 3 和 4 压入堆栈
* 2、遇到 + 运算符，因此弹出 4 和 3 ，计算出 3 + 4 = 7，在将 7 压入栈
* 3、将 5 入栈
* 4、接下来是 * 运算符，因此弹出 5 和 7，计算出 7 * 5 = 35，将 35 压栈
* 5、将 6 入栈
* 6、最后是 - 运算符，计算出 35 - 6 = 29，最后把 29 压入栈
* <p>
* 这就是后缀表达式计算思路，但是如何把 [中缀表达式] 转为 [后缀表达式]
* <p>
* [中缀表达式] 转为 [后缀表达式]
* 后缀表达式：适合计算式进行运算，但是不适合人的书写
* 中缀表达式：适合人的书写，但是不适合计算式运算
* 所以需要把 [中缀表达式] 转为 [后缀表达式]
* 思路：
* 1、初始化两个栈：运算符栈（s1）和 存储中间结果的栈（s2）
* 2、从左到右扫描中缀表达式
* 3、遇到操作数时，将其压s2
* 4、遇到运算符时，与 s1 栈顶的运算符比较优先级
* 4.1、如果 s1 为空，或栈顶运算符为左括号"("，则直接将此运算符入栈
* 4.2、否则，若优先级比栈顶运算符的高，也将运算符压入s1
* 4.3、否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到 4.1 与 s1 中新的栈顶运算符相比较
* 5、遇到括号时
* 5.1、如果是左括号"("，则直接压入s1
* 5.2、如果是右括号")"，则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到左括号为止，此时将这一对括号丢弃
* 6、重复步骤 2~5，直到表达式的最右侧
* 7、将 s1 中剩余的运算符依次弹出并压入 s2
* 8、依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
*/
public class PolandNotation {
/**
* 计算器
*
* @param poland
* @return
*/
public static Integer calculatorPoland(List<String> poland) {
return Operation.calculator(poland);
}
/**
* 例如：(3+4)*5-6 对应的后缀表达式就是 3 4 + 5 * 6 -
* [中缀表达式] 转为 [后缀表达式]
* 后缀表达式：适合计算式进行运算，但是不适合人的书写
* 中缀表达式：适合人的书写，但是不适合计算式运算
* 所以需要把 [中缀表达式] 转为 [后缀表达式]
* 思路：
* 1、初始化两个栈：运算符栈（s1）和 存储中间结果的栈（s2）
* 2、从左到右扫描中缀表达式
* 3、遇到操作数时，将其压s2
* 4、遇到运算符时，与 s1 栈顶的运算符比较优先级
* 4.1、如果 s1 为空，或栈顶运算符为左括号"("，则直接将此运算符入栈
* 4.2、否则，若优先级比栈顶运算符的高，也将运算符压入s1
* 4.3、否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到 4.1 与 s1 中新的栈顶运算符相比较
* 5、遇到括号时
* 5.1、如果是左括号"("，则直接压入s1
* 5.2、如果是右括号")"，则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到左括号为止，此时将这一对括号丢弃
* 6、重复步骤 2~5，直到表达式的最右侧
* 7、将 s1 中剩余的运算符依次弹出并压入 s2
* 8、依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
*/
public static List<String> parsePoland(String ls) {
// 运算符栈（s1）
Stack<String> s1 = new Stack<>();
// 存储中间结果的栈（s2）
List<String> list = new ArrayList<>();
// 去除空格
String trim = ls.trim();
Integer index = 0;
// 拼接多位数
StringBuilder numBuilder = null;
while (index < trim.length()) {
String sub = trim.substring(index, index + 1);
System.out.println("index = " + index + " sub = " + sub);
// 3、遇到操作数时，将其压s2
if (sub.matches("\\d+")) {
numBuilder = new StringBuilder("");
while (sub.matches("\\d+") && index < trim.length()) {
numBuilder.append(sub);
index++;
if (index < trim.length()) {
sub = trim.substring(index, index + 1);
}
}
list.add(numBuilder.toString());
// 减去 while 中的 ++
index--;
}
// 4、遇到运算符时，与 s1 栈顶的运算符比较优先级
else if (Operation.isOperation(sub)) {
while (true) {
// 4.1、如果 s1 为空，或栈顶运算符为左括号"("，则直接将此运算符入栈
if (s1.isEmpty() || s1.peek().equals("(")) {
s1.push(sub);
break;
}
// 4.2、否则，若优先级比栈顶运算符的高，也将运算符压入s1
else if (Operation.priority(sub) > Operation.priority(s1.peek())) {
s1.push(sub);
break;
}
// 4.3、否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到 4.1 与 s1 中新的栈顶运算符相比较
else {
list.add(s1.pop());
}
}
}
// 5、遇到括号时
// 5.1、如果是左括号"("，则直接压入s1
else if (sub.equals("(")) {
s1.push(sub);
}
// 5、遇到括号时
// 5.2、如果是右括号")"，则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到左括号为止，此时将这一对括号丢弃
else if (sub.equals(")")) {
while (!s1.peek().equals("(")) {
list.add(s1.pop());
}
// 丢弃 s1 的左括号
s1.pop();
}
index++;
}
// 7、将 s1 中剩余的运算符依次弹出并压入 s2
while (!s1.isEmpty()) {
list.add(s1.pop());
}
// 8、依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
return list;
}
}
/**
* 操作
*/
class Operation {
/**
* 判断是否为操作符
*/
public static Boolean isOperation(String item) {
return "+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item);
}
/**
* 判断操作符的优先级
*/
public static int priority(String item) {
switch (item) {
case "+":
case "-":
return 1;
case "*":
case "x":
case "/":
return 2;
default:
throw new RuntimeException("操作符错误");
}
}
/**
* 判断操作符的优先级
* 3 4 + 5 * 6 -
*/
public static Integer calculator(List<String> poland) {
Integer res = 0;
Stack<String> stack = new Stack<>();
for (String item : poland) {
// 如果是数字
if (item.matches("\\d+")) {
stack.push(item);
} else {
int num1 = Integer.parseInt(stack.pop());
int num2 = Integer.parseInt(stack.pop());
switch (item) {
case "+":
res = num1 + num2;
break;
case "-":
res = num2 - num1;
break;
case "*":
case "x":
res = num1 * num2;
break;
case "/":
res = num2 / num1;
break;
default:
throw new RuntimeException("操作符错误");
}
// 结果入栈
stack.push(res.toString());
}
}
return res;
}
}
网友评论