This is a series of calculator problems:
- 227. Basic Calculator II
- 224. Basic Calculator
- 772. Basic Calculator III(Premium): Which contains
+-*/and()operations, and the number can be more than one digit.
Before solving this problem, we can break down the problems into several parts:
val s = "1234"
var num = 0
for (c in s) {
num = num * 10 + (c - '0')
}
return numFor s = 300 + 10 - 5, how to calculate the addition and subtraction? We can break down the steps:
- We can trim the space and append a
+at the beginning of the string:+300+10-5 - The idea to solve this problem is that we treat every item as [
operatorandnumber]. We parse the number and operator pairs:+300,+10,-5, then push into stack. - We sum up all the elements in the stack:
300 + 10 - 5 = 305
There is a special case: The last number, we also have to push it into the stack.
fun calculate(s: String): Int {
val stack = Stack<Int>()
var num = 0
var sign = '+' // We initialize the sign as `+` at the beginning of the string
for (i in 0 until s.length) {
val c = s[i]
if (c.isDigit()) {
num = num * 10 + (c - '0')
}
// If the character is a operator or the last number, see below explanation:
// +300+ ...
// c We should push +300 into the stack
// -5
// c We should push -5 into the stack for the
if ((!c.isDigit() && c != ' ') || i == s.lenght - 1) {
// We push the operator and number into the stack when we encounter the next operator (current index i)
// This is the previous sign and the number next to it
when (sign) {
'+' -> stack.push(num)
'-' -> stack.push(-num)
}
// Update to the current sign
sign = c
// Reset the number for the next number
num = 0
}
}
// Stack: [+0, +300, +10, -5]
var sum = 0
while (stack.isNotEmpty()) {
sum += stack.pop()
}
return sum
}Let's explain the code:
...
// 300 + 10 - 5
// ^ i is here, next to `+10`
if (!c.isDigit() && c != ' ' || i == s.lenght - 1) {
// Push `+10` into stack
when (sign) { // sign = `+` before 10
'+' -> stack.push(num) // num = 10
'-' -> stack.push(-num)
}
// Update to the current sign
sign = c // sign = `-` before 5
// Reset the number for the next number
num = 0
}
...
```js
i
_ 300 + 10 - 5
| |
| num = 300
sign = + // We initialize the sign as `+` at the beginning of the string
// Next operator
i
300 + 10 - 5
| |
| num = 10
sign = +After understanding the above concepts, now we can solve the original problem. The difference between this problem and the previous one is that we have to calculate the multiplication and division first, then sum up all the elements in the stack.
We still trim the space and append a "+" at the beginning of the string, and parse the string as [operator and number], for example, 3 - 2 * 5 / 2 + 7 will be +3, -2, *5, /2, +7. Then we calculate all the results of * and / first which has high priority than + and -, and then every item will be a plus or minus numbers that have the same priority, we can sum them up to get the result.
Based on this idea, w can iterate the string and parse the number after the operator:
- If the operator is
+or-, we push the number into the stack. - If the operator is
*or/, because we have to calculate the result immediately which*and/, we pop the last number from the stack, calculate the result, and push it back to the stack. This is how we calculate the multiplication and division first.
s = "3 - 2 * 5 / 2 + 7"
// Trim the space and append a "+" at the beginning of the string
s = "+3-2*5/2+7"
s = "+3-2*5/2+7"
^^ // Push +3 into stack
stack = [+0, +3]
s = "+3-2*5/2+7"
^^ // Push -2 into stack
stack = [+0, +3, -2]
s = "+3-2*5/2+7"
^^
stack = [+0, +3, -10] // We pop -2 and calculate -2 * 5 = -10, then push -10 back to stack
s = "+3-2*5/2+7"
^^
stack = [+0 +3, -5] // We pop -10 and calculate -10 / 2 = -5, then push -5 back to stack
s = "+3-2*5/2+7"
^^ // Push +7 into stack
stack = [+0, +3, -5, +7]
// Sum up all the elements in stack: 3 - 5 + 7 = 5
return 5 fun calculate(s: String): Int {
val stack = Stack<Int>()
var num = 0
var operation: Char = '+'
val operationSet = hashSetOf('+', '-', '*', '/')
for (i in 0 until s.length) {
val c = s[i]
if (c.isDigit()) {
// Wrong to use `c.toInt()` is the ASCII code of the character, not the number
num = num * 10 + (c - '0')
}
if (operationSet.contains(c) || i == s.length - 1) {
when (operation) {
'+' -> {
stack.push(num)
}
'-' -> {
stack.push(-num)
}
'*' -> {
stack.push(stack.pop() * num)
}
'/' -> {
stack.push(stack.pop() / num)
}
}
operation = c
num = 0
}
}
var sum = 0
while (stack.isNotEmpty()) {
sum += stack.pop()
}
return sum
}How does this code work when we have
-at the beginning of the string?
s = "-5 + 3"
num = 0
operation = '+'
stack = []
c = '-' // Is operation
stack = [+0] // We push current operation '+' and num '0' into the stack
operation = '-'
num = 0
c = '5' // Is digit
num = 5
c = '+' // Is operation
stack = [+0, -5] // We push the previous operation '-' and num '5' into the stack
c = '3' // Last index
stach = [+0, -5, +3] // We push the current operation '+' and num '3' into the stackOr equivalently, we can use the following code to calculate the result:
- We do really append
+at the beginning of the string and trim the space. - We iterate the string and parse the [
operatorandnumber], then push them into the stack. (For*and/, we have to calculate the result immediately) - We sum up all the elements in the stack.
fun calculate(str: String): Int {
val s = "+" + str.replace("\\s+".toRegex(), "")
val stack = Stack<Int>()
var i = 0
while (i < s.length) {
val c = s[i]
if (c == '+' || c == '-') {
// Parse the number after the operator
var num = 0
while (i + 1 < s.length && s[i + 1].isDigit()) {
i++
num = num * 10 + (s[i] - '0')
}
if (c == '+') {
stack.push(num)
} else {
stack.push(-num)
}
} else if (c == '*' || c == '/') {
// Parse the number after the operator
var num = 0
while (i + 1 < s.length && s[i + 1].isDigit()) {
i++
num = num * 10 + (s[i] - '0')
}
val last = stack.pop()
if (c == '*') {
stack.push(last * num)
} else {
stack.push(last / num)
}
}
i++
}
// There is no `*` and `/` in the stack, we can sum up all the elements in the stack
var sum = 0
while (stack.isNotEmpty()) {
sum += stack.pop()
}
return sum
}Or we can split by operator and number to get the numbers and operators, then we can the apply the same idea to calculate the result.
This approach may not work correctly if we have leading negative numbers, for example,
-5 + 3. We could append a leading "0" to the string to avoid this issue.
s = "3 - 2 * 5 / 2 + 7"
operators = s.split(number) = ["", "-", "*", "/", "+", ""] // Note that the first and last element are empty
numbers = s.split(operator) = ["3", "2", "5", "2", "7"]
// We hope to calculate in the following ways:
0 1 2 3 4
[ "" ,"-", "*", "/", "+", ""]
["3", "2", "5", "2", "7"]
i ->
3, -2, *5, /2, +7
// Then we can apply the same idea to calculate the resultfun calculate(str: String): Int {
val s = str.replace("\\s+".toRegex(), "")
val operators = s.split("\\d+".toRegex())
val nums = s.split("[+\\-*/]".toRegex()).map { it.toInt() }
val stack = Stack<Int>()
stack.push(nums[0].toInt())
for (i in 1 until nums.size) {
val num = nums[i]
val op = operators[i]
if (op == "+") {
stack.push(num)
} else if (op == "-") {
stack.push(-num)
} else if (op == "*") {
stack.push(stack.pop() * num)
} else if (op == "/") {
stack.push(stack.pop() / num)
}
}
var sum = 0
while (stack.isNotEmpty()) sum += stack.pop()
return sum
}https://leetcode.cn/problems/basic-calculator-ii/solutions/91271/chai-jie-fu-za-wen-ti-shi-xian-yi-ge-wan-zheng-ji-/ (There contains the solution to 772. Basic Calculator III)