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 num概念就是遇到一個新的運算符，會把「前一個」的運算符 + 數字壓入 stack，然後才更新成現在的運算符。
For s = 300 + 10 - 5, how to calculate? There are some key ideas:
- We treat every item as [
operatorandnumber]:+300,+10,-5 - We push the number before the operator into the stack: We iterate the string (skip the space) and parse the number until the next operator or the end of the string, then push the number into the stack.
- We sum up all the elements in the stack:
[+300, +10, -5] = 305
Please mind the special case: The last number, because there is no operator after the last number, we also have to push it into the stack.
For example, s = "300 + 10 - 5", the iteration process is:
s = "300 + 10 - 5"
i
// 1. Before iteration:
num = 0
operator = '+'
stack = []
s = "300 + 10 - 5"
i
// 2. After parsing 300, encountering `+`:
num = 300
operator = '+' // The operator for 300
stack = [+300]
operator = '+' // Update the operator after 300
s = "300 + 10 - 5"
i
// 3. After parsing 10, encountering `-`:
num = 10
operator = '+' // The operator for 10
stack = [+300, +10]
operator = '-' // Update the operator after 10Question: What if we have
-300 + 10 ..., the starting number is negative?
我們遇到 - 會先把前一個 +0 壓入 (初始化的 operator = + + num = 0) 堆疊後才會更新 operator = -。
The key difference is that we will push +0 (the initial and "invisible" number before -) into the stack when encountering the first - at the beginning:
s = "-300 + 10 - 5"
i
// Before iteration:
num = 0
operator = '+'
stack = []
s = "-300 + 10 - 5"
i
// Encountering `-`:
num = 0
operator = '+' // The operator for 0
stack = [+0]
operator = '-' // Update the operator after 0, that is `-` for `-300`
// After parsing -300, encountering `+`:
Same as above.
stack = [+0, -300]
// The remaining process is the same as above.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 since there is no further operator that can trigger the push.
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
}In the original problem, we must evaluate *, / before +, -. And our ultimate goal is to reduce the entire expression into a collection of postive and negative numbers that can sum up directly without considering the different evaluation priority.
When reading an operator like +, -, *, /, we can't use it right away, we need "hold onto" and read the next number, then apply the saved operator. The key idea is to remember the past operator and apply it only when we hit the next operator.
Stack is a good fit to easily hold and retrieve the most recent number. It stores the numbers that are waiting to apply the operator together at the very end. And for the state updates is to track the previous operators, not the current one.
- 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.
我們必須牢記剛剛的邏輯：「遇到新的運算符，就會把前一個運算符 + 數字壓入堆疊」，然後運算符才更新為現在新的。」
所以以下要注意
num,operator,c的更新:
c是目前遇到的運算符。num,operator都是「前一個」的。在
A * B - ...Key!! 我們遇到*還不會做什麼事情，只會單純把A加入堆疊。直到遇到-的時候會把A從堆疊拿出來乘上B之後加回堆疊。
fun calculate(s: String): Int {
val stack = Stack<Int>()
var num = 0
var lastOperator: Char = '+'
val operators = 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')
}
// Here we can't use `else if` because we have to push the last number into the stack
if (operators.contains(c) || i == s.length - 1) {
// `c` is the current operator, and `lastOperator` is the previous operator
// We push previous operator and number into the stack.
when (lastOperator) {
'+' -> {
stack.addLast(num)
}
'-' -> {
stack.addLast(-num)
}
'*' -> {
stack.addLast(stack.removeLast() * num)
}
'/' -> {
stack.addLast(stack.removeLast() / num)
}
}
// Update to the current operator
lastOperator = c
// Reset the number for the next number
num = 0
}
}
return stack.sum()
}// 1. Initialization: num = 0, operator = '+'
s = "+3-2*5/2+7"
// 2. num = 3, operator = '+', c = '-'
s = "+3-2*5/2+7"
^^
stack = [+0, +3] // Push +3 into stack
// 3. num = 2, operator = '-', c = '*'
s = "+3-2*5/2+7"
^^
stack = [+0, +3, -2] // Push -2 into stack
// 4. num = 5, operator = '*', c = '/'
s = "+3-2*5/2+7"
^^
stack = [+0, +3, -10] // We pop -2 and calculate -2 * 5 = -10, then push -10 back to stack
// 5. num = 2, operator = '/', c = '+'
s = "+3-2*5/2+7"
^^
stack = [+0 +3, -5] // We pop -10 and calculate -10 / 2 = -5, then push -5 back to stack
// 6. Last index, num = 7, operator = '+'
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 We can apply the same idea above without using a stack, we just need a running sum and a lastNumber variable:
- When we encounter
+or-, the previous operations is "completed", we can add thelastNumberto thesum, and updatelastNumberto the current number with the correct sign. - When we encounter
*or/, we don't update thesum, we simply calculate the multiplication or division with thelastNumberand updatelastNumberto the result, holding it in place until the next operator or the end of the string.
fun calculate(s: String): Int {
var sum = 0
var lastOperator = '+'
var lastNumber = 0
var currentNumber = 0
for (i in s.indices) {
val c = s[i]
if (c.isDigit()) {
currentNumber = currentNumber * 10 + (c - '0')
}
if (c in operators || i == s.length - 1) {
when (lastOperator) {
'+' -> {
sum += lastNumber
lastNumber = currentNumber
}
'-' -> {
sum += lastNumber
lastNumber = -currentNumber
}
// 3 x 5 - 2
// stack.last(), op, num, c
'*' -> lastNumber = lastNumber * currentNumber
'/' -> lastNumber = lastNumber / currentNumber
}
lastOperator = c
currentNumber = 0
}
}
// Remember to add the last number to the sum at the end, for "3 * 5 * 2".
sum += lastNumber
return sum
}Might skip the following approaches.
- We do really append
+at the beginning of the string and trim the space. Now the formula becomes+3, -2, *5, /2, +7, which is exactly the pattern(operator, number). - Then iterate the string to find an operator, and parse the number after it.
- Apply the operator (and combine it with the stack for
*and/), then update the operator to the current one.
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)