简单计算器的实现-逆波兰表达式
一般也就是分为两步
- 将中缀表达式 解析为 后缀(前缀)表达式
- eval 计算后缀表达式解析 出 结果
- 中缀表达式
一般的算数表达式, 操作符以中缀形式出现在操作数之间
- 前缀表达式
前缀表达式是一种没有括号的算术表达式,与中缀表达式不同的是，其将运算符写在前面，操作数写在后面.
为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为波兰式.
- 后缀表达式
后缀表达式指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,
严格从左向右进行(不再考虑运算符的优先规则). 也称为 逆波兰表达式
中缀表达式: 1-(2+3)
前缀表达式: 1 2 3 + -
后缀表达式: - 1 + 2 3
中缀表达式 转 前缀表达式
((a+(b*c))+(((d*e)+f)*g)
前缀表达式
++a*bc*+*efg同样是使用栈的方式解析, 前缀表达式的解析 和 后缀表达式的解析 方式相反, 从右向左
- 解析 中缀表达式
从右至左解析中缀表达式
- 遇到数字 直接输出
- 遇到操作符
2.1 ‘)’直接入栈
2.2 ‘(‘ 将符号栈中元素移除并输出, 直到遇到右括号)只移除,不输出
2.3 运算符: 将符号栈中的元素移除出栈并输出, 直到遇到比当前符号优先级更高的符号或者).
将当前符号入栈
3. 扫描完后, 将栈中剩余符号依次输出
for example
下面以a+b*c+(d*e+f)*g为例子来看看转换过程:
面在描述栈的情况是直接用文字描述了,由左到右为栈底到栈顶.空表示栈空
1. 从后向左遍历表达式: g
输出: g
符号栈:
2. 从后向左遍历表达式: *
输出: g
符号栈: *
3. 从后向左遍历表达式: )
输出: g
符号栈: )*
4. 从后向左遍历表达式: f
输出: fg
符号栈: )*
5. 从后向左遍历表达式: +
输出: fg
符号栈: +)*
6. 从后向左遍历表达式: e
输出: efg
符号栈: +)*
7. 从后向左遍历表达式: *
输出: efg
符号栈: *+)*
8. 从后向左遍历表达式: d
输出: defg
符号栈: *+)*
9. 从后向左遍历表达式: (
输出: +*defg
符号栈: *
10. 从后向左遍历表达式: +
输出: *+*defg
符号栈: +
11. 从后向左遍历表达式: c
输出: c*+*defg
符号栈: +
12. 从后向左遍历表达式: *
输出: c*+*defg
符号栈: *+
13. 从后向左遍历表达式: b
输出: bc*+*defg
符号栈: *+
14. 从后向左遍历表达式: +
输出: *bc*+*defg
符号栈: ++
15. 从后向左遍历表达式: a
输出: a*bc*+*defg
符号栈: ++
16. 将符号栈中剩余的 符号压入 结果集
输出: ++a*bc*+*defg
符号栈:
- 解析 前缀表达式
/**
* 基本计算器3 </br>
*
* @author majunmin
* @description
* @datetime 2021-09-25 19:47
* @since
*/
public class LeetCode_0772 implements Solution {
@Override
public int calculate(String s) {
List<String> pe = parsePE(s);
int res = evalPE(pe);
return res;
}
private List<String> parsePE(String s) {
List<String> list = new LinkedList<>();
Deque<String> opStack = new LinkedList<>();
final char[] chars = s.toCharArray();
int num = -1;
for (int i = chars.length - 1; i >= 0; i--) {
char c = chars[i];
if (c == ' ') {
continue;
}
if (c >= '0' && c <= '9') {
if (num == -1) {
num = c - '0';
} else {
num = num + (c - '0') * 10;
}
} else {
if (num != -1) {
list.add(0, String.valueOf(num));
num = -1;
}
if (c == ')') {
opStack.push(")");
} else if (c == '(') {
while (!Objects.equals(opStack.peek(), ")")) {
list.add(0, opStack.pop());
}
opStack.pop();
} else {
// 运算符
String op = String.valueOf(c);
while (!opStack.isEmpty()) {
if (Objects.equals(opStack.peek(), ")")) {
break;
}
if (getPriority(op) >= getPriority(opStack.peek())) {
break;
}
list.add(0, opStack.pop());
}
opStack.push(op);
}
}
}
if (num != -1) {
list.add(0, String.valueOf(num));
}
while (!opStack.isEmpty()) {
list.add(0, opStack.pop());
}
return list;
}
/**
* 解析 波兰表达式
* ++a*bc**+*efg
*
* @param pe
* @return
*/
private int evalPE(List<String> pe) {
Deque<String> stack = new LinkedList<>();
// 从右向左遍历
for (int i = pe.size() - 1; i >= 0; i--) {
String curStr = pe.get(i);
if (curStr.charAt(0) >= '0' && curStr.charAt(0) <= '9') {
stack.push(curStr);
} else {
int num = 0;
int num1 = parseInt(stack.pop());
int num2 = parseInt(stack.pop());
switch (curStr) {
case "+":
num = num1 + num2;
break;
case "-":
num = num1 - num2;
break;
case "*":
num = num1 * num2;
break;
case "/":
num = num1 / num2;
break;
default:
throw new IllegalArgumentException("Unexcept error.");
}
stack.push(String.valueOf(num));
}
}
return parseInt(stack.pop());
}
/**
* 将中最表达式转化为 逆波兰表达式
* 1. 遇到数字直接 放入 list
* 2. 遇到 符号
* 2.1 `(` 直接放入
* 2.2 `)` 将栈中 所有的字符 pop 放入到结果集
* 2.3 `符号`
* 2.3.1 符号优先级 <= 栈顶元素优先级,直接放入
* 2.3.2 符号优先级 > 栈顶元素优先级,将栈中元素pop 并放入结果集, 直到遇到 `(` 或者 栈 为空
*
* @param s
* @return
*/
private List<String> parseRPE(String s) {
List<String> rpe = new ArrayList<>();
Deque<String> stack = new LinkedList<>();
int num = -1;
for (char c : s.toCharArray()) {
if (c == ' ') {
continue;
}
// 是一个数字
if (c >= '0' && c <= '9') {
if (num == -1) {
num = c - '0';
} else {
num = num * 10 + (c - '0');
}
} else {
//判断数字
if (num != -1) {
rpe.add(String.valueOf(num));
num = -1;
}
if (c == '(') {
stack.push(String.valueOf(c));
} else if (c == ')') {
while (!stack.isEmpty()) {
if (!"(".equals(stack.peek())) {
rpe.add(stack.pop());
} else {
stack.pop();
break;
}
}
} else {
// + - * /
while (!stack.isEmpty()) {
if ("(".equals(stack.peek())) {
break;
}
if (getPriority(String.valueOf(c)) > getPriority(stack.peek())) {
break;
}
rpe.add(stack.pop());
}
stack.push(String.valueOf(c));
}
}
}
if (num != -1) {
rpe.add(String.valueOf(num));
}
while (!stack.isEmpty()) {
rpe.add(stack.pop());
}
return rpe;
}
private int getPriority(String op) {
switch (op) {
case "+":
case "-":
return 1;
case "*":
case "/":
return 2;
default:
throw new IllegalArgumentException("Unexpected value: " + op);
}
}
}中缀表达式 转 后缀表达式
((a+(b*c))+(((d*e)+f)*g)
后缀表达式
abc*+de*f+g*+使用栈的方式解析,解析步骤:
从左到右扫描中缀表达式,
- 遇到数字直接输出
- 遇到运算符
2.1 ‘(‘ 直接入栈
2.2 ‘)’ 将符号栈中的元素移除出栈并输出, 直到 (, ( 只出栈,不输出
2.3 +-*/: 将符号栈中的元素移除出栈并输出, 直到遇到比当前符号优先级更低的符号或者’(‘.
将当前符号入栈
3. 扫描完后, 将栈中剩余符号依次输出
for example:
下面以a+b*c+(d*e+f)*g为例子来讲讲计算机的转换过程下.
面在描述栈的情况是直接用文字描述了,由左到右为栈底到栈顶.空表示栈空
1. 由左向右遍历表达式,首先遇到a,直接将其输出.
此时输出为：a
栈的情况为：空
2. 继续遍历,遇到+,将其放入栈中.
此时输出为：a
栈的情况为：+
3. 继续遍历,遇到b,直接将其输出.
此时输出为：ab
栈的情况为：+
4. 继续遍历，遇到*，因为*的优先级大于栈顶的+，所以将*放入栈内。
此时输出为：ab
栈的情况为：+*
5. 继续遍历,遇到c,直接将其输出.
此时输出为：abc
栈的情况为：+*
6. 继续遍历,遇到+,因为+的优先级低于栈顶的*, 故将*弹出; 然后新的栈顶元素的+与这个+优先级相同, 故也要弹出现在栈顶的+;然后栈空了,将现在这个+放入栈中
此时输出为：abc*+
栈的情况为：+
7. 继续遍历,遇到(,直接将其放入栈中,不遇到)不会将(弹出
此时输出为：abc*+
栈的情况为：+(
8. 继续遍历,遇到d,直接将其输出.
此时输出为：abc*+d
栈的情况为：+(
9. 继续遍历,遇到*,因为栈顶为(,不遇到)不将(弹出,故直接将*放入栈中
此时输出为：abc*+d
栈的情况为：+(*
10. 继续遍历，遇到e，直接将其输出。
此时输出为：abc*+de
栈的情况为：+(*
11. 继续遍历，遇到+，因为+比栈顶*的优先级低，故将*弹出；新的栈顶元素为(,不遇到)不弹出(,故将+放入栈中。
此时输出为：abc*+de*
栈的情况为：+(+
12. 继续遍历，遇到f，直接将其输出。
此时输出为：abc*+de*f
栈的情况为：+(+
13. 继续遍历，遇到),直接将栈中元素依次弹出并输出直到遇到(为止, 注意：(弹出但不输出
此时输出为：abc*+de*f+
栈的情况为：+
14. 继续遍历，遇到*，因为*的优先级大于栈顶元素+的优先级，故直接将*入栈。
此时输出为：abc*+de*f+
栈的情况为：+*
15. 继续遍历，遇到g，直接将其输出。
此时输出为：abc*+de*f+g
栈的情况为：+*
16. 继续遍历，为空，遍历结束。将栈内元素依次弹出。
此时输出为：abc*+de*f+g*+
栈的情况为：空至此，中缀表达式转后缀已经全部完成,结果为abc*+de*f+g*+
解析 会解析后缀表达就很简单了
leetCode 772：
/**
* 基本计算器3 </br>
*
* @author majunmin
* @description
* @datetime 2021-09-25 19:47
* @since
*/
public class LeetCode_0772 implements Solution {
@Override
public int calculate(String s) {
List<String> rpe = getRPE(s);
int result = eval(rpe);
return result;
}
/**
* rpe 表达式仅包含 {@text 数字 +-/*}
*
* @param rpe
* @return
*/
private int eval(List<String> rpe) {
Deque<String> stack = new LinkedList<>();
for (String item : rpe) {
if (item.charAt(0) >= '0' && item.charAt(0) <= '9') {
stack.push(item);
} else {
int num1 = parseInt(stack.pop());
int num2 = parseInt(stack.pop());
int result;
if (!validOperator(item)) {
throw new IllegalArgumentException("");
}
switch (item) {
case "+":
result = num2 + num1;
break;
case "-":
result = num2 - num1;
break;
case "*":
result = num2 * num1;
break;
default:
result = num2 / num1;
break;
}
stack.push(String.valueOf(result));
}
}
return Integer.parseInt(stack.pop());
}
private boolean validOperator(String operator) {
return "+".equals(operator) || "-".equals(operator)
|| "*".equals(operator) || "/".equals(operator);
}
private int parseInt(String item) {
return Integer.parseInt(item);
}
/**
* 将中最表达式转化为 逆波兰表达式
* 1. 遇到数字直接 放入 list
* 2. 遇到 符号
* 2.1 `(` 直接放入
* 2.2 `)` 将栈中 所有的字符 pop 放入到结果集
* 2.3 `符号`
* 2.3.1 符号优先级 <= 栈顶元素优先级,直接放入
* 2.3.2 符号优先级 > 栈顶元素优先级,将栈中元素pop 并放入结果集, 直到遇到 `(` 或者 栈 为空
*
* @param s
* @return
*/
private List<String> getRPE(String s) {
List<String> rpe = new ArrayList<>();
Deque<String> stack = new LinkedList<>();
int num = -1;
for (char c : s.toCharArray()) {
if (c == ' ') {
continue;
}
// 是一个数字
if (c >= '0' && c <= '9') {
if (num == -1) {
num = c - '0';
} else {
num = num * 10 + (c - '0');
}
} else {
//判断数字
if (num != -1) {
rpe.add(String.valueOf(num));
num = -1;
}
if (c == '(') {
stack.push(String.valueOf(c));
} else if (c == ')') {
while (!stack.isEmpty()) {
if (!"(".equals(stack.peek())) {
rpe.add(stack.pop());
} else {
stack.pop();
break;
}
}
} else {
// + - * /
while (!stack.isEmpty()) {
if ("(".equals(stack.peek())) {
break;
}
if (getPriority(String.valueOf(c)) > getPriority(stack.peek())) {
break;
}
rpe.add(stack.pop());
}
stack.push(String.valueOf(c));
}
}
}
if (num != -1) {
rpe.add(String.valueOf(num));
}
while (!stack.isEmpty()) {
rpe.add(stack.pop());
}
return rpe;
}
private int getPriority(String op) {
switch (op) {
case "+":
case "-":
return 1;
case "*":
case "/":
return 2;
default:
throw new IllegalArgumentException("Unexpected value: " + op);
}
}
public static void main(String[] args) {
Solution leetCode = new LeetCode_0772();
System.out.println(leetCode.calculate("6 - 4/2"));
System.out.println(leetCode.calculate("(2 + 6*3 +5 - (3*14/7+2) *5)+3"));
}
}