中缀表达式转后缀表达式,计算后缀表达式实现的加减乘除括号计算器。

思路

中缀表达式转后缀表达式,计算后缀表达式。

中缀转后缀

  • 数字
    • 直接添加到结果
  • 非数字
    • ” )“,依次弹栈添加到结果直到“( ”(左括号也弹栈)
    • “( “直接压栈,不用管
    • 判断是否低于栈顶符号,大于直接入栈,等于先弹栈再入栈,低于直接弹栈到字符优先级高于栈顶符号或者左括号或空栈

后缀计算

  • 数字
    • 入栈
  • 非数字
    • 根据字符进行两次出栈操作然后计算完再入栈

实现

中缀转后缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
* 优先级
* 加减优先级最低
* 然后就是乘除
* 括号优先级最高
* */
val priority = mapOf(
"+" to 0,
"-" to 0,
"*" to 1,
"/" to 1,
"(" to 2,
")" to 2
)

/**
* 中缀转后缀
* */
private fun infixToPostfix(expr: String): String {
val sb = StringBuilder()
val s = Stack<Char>()

expr.forEach { c: Char ->
when (c) {
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9' -> sb.append(c)
'+', '-', '*', '/' -> {
while (!s.isEmpty()
&& s.peek() != '('
&& priority[c.toString()]!! <= priority[s.peek().toString()]!!
) {
sb.append(s.pop())
}
s.push(c)
}
'(' -> s.push(c)
')' -> {
while (!s.isEmpty()) {
if (s.peek() == '(') {
s.pop()
break
} else {
sb.append(s.pop())
}
}
}
else -> throw UnsupportedOperationException("未知字符!")
}
}
while (!s.isEmpty()) {
sb.append(s.pop())
}
return sb.toString()
}

计算后缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 计算后缀表达式
* */
private fun evalPostfix(expr: String): Double {
val s = Stack<Double>()
expr.forEach { c: Char ->
when (c) {
'+' -> s.pop().plus(s.pop()).let { s.push(it) }
'-' -> s.pop().minus(s.pop()).let { s.push(it) }
'*' -> s.pop().times(s.pop()).let { s.push(it) }
'/' -> s.pop().div(s.pop()).let { s.push(it) }
else -> s.push(Character.getNumericValue(c).toDouble())
}
}
return if (s.isEmpty()) 0.0 else s.pop()
}

主函数

1
2
3
4
5
/**
* 四则运算(带括号)
* */
fun evalIntArithmetic(expr: String): Double =
evalPostfix(infixToPostfix(expr.trim().replace(" ", "")))

测试

1
2
3
4
5
6
7
8
9
package fundamentals

import utils.evalIntArithmetic

fun main() {
println(evalIntArithmetic(""))
println(evalIntArithmetic(" 1 + 2"))
println(evalIntArithmetic("1+2*3+(4*5+6)*7"))
}

输出:

image-20200712185745469
image-20200712185745469

验算:

image-20200712185812495
image-20200712185812495

Github

Github