With parentheses which affects precedence: 1 + (6 + 8) - 99, we need to evaluate the expression inside the parentheses first, while remembering the context outside the parentheses.
In 227. Basic Calculator II, precedence was dictated by the operator
*and/. Here it's dictated purely by scope (parentheses). Because the parentheses can be nested infinitely, the underlying structure is inherently recursivie.
- Subproblem: We treat everything inside the parentheses as it's own isolated calculator problem,
- Saving state: When encoutering
(, we need to pause the current evaluation, then save the current state (running result and sign before the parentheses), then reset them for the subproblem inside the parenthesses. - Data structure: We need a data structure to store the previous evaluation result and the sign when we encounter
(and pop to combine it with the result of subproblem when when we hit)to, we can use a stack for this.
Here we define some variable during evaluation:
numfor the current parsed number.signfor the current sign.resultfor the current running evaluation.
For this basic calculator -5 + 8 - (4 + 2), there are several cases we need to consider:
- The number: We need to build the number from digits. Mind the number can be more than one digit.
- The operator
+/-: We need to calculate the result based on the operator.- Here please note that we apply the same login in 227. Basic Calculator II to sum up the previous result when we encounter the new operator.
-, 5 +, 8 -, (, 4 +, 2, )
num = 0 0 5 0 8 8
sign = 1 -1 -1 1 1 -1
result = 0 0 0 5 3 3
^ // sum up `-5` to result
^ // sum up `+8` to result
stack = []- Open parenthesis
(: It's the start of a subproblem. We start to calculate the result inside the parenthese.- Pause the current result and sign
+before the parenthese by pushing into the stack. - Reset the
resultandsignfor the calculation inside the parenthese.
- Pause the current result and sign
-, 5 +, 8 -, (, 4 +, 2, )
num = 0 0 5 0 8 8 0 4 0 2
sign = 1 -1 -1 1 1 -1 1 1 1 1
result = 0 0 0 5 3 3 0 0 4 4
stack = [3, -1]- Close parenthesis
): We finish calculating the result inside the parenthese.- Combine the previous result (from stack) with the current result (variables) inside the parenthese.
- Then push the combined result back to the stack
- Reset the
resultandsignfor the calculation after the parenthese.
-, 5 +, 8 -, (, 4 +, 2, )
num = 0 0 5 0 8 8 0 4 0 2 0
sign = 1 -1 -1 1 1 -1 1 1 1 1 1
result = 0 0 0 5 3 3 0 0 4 4 6
stack = [3, -1]
result = 3 + -1 * 6 = -3fun calculate(s: String): Int {
val stack = Stack<Int>()
// The current evaluation
var result = 0
// The current operand builder
var number = 0
// +/- symbol
var sign = 1
for (i in 0 until s.length) {
if (s[i].isDigit()) {
// Build the current number from digits
number = number * 10 + (s[i] - '0')
}
else if (s[i] == '(') {
// XYZ +/- (
// Cache the current result XYZ and sign before parenthese
stack.push(result)
stack.push(sign)
// Reset all state and use them to calculate the value inside parenthese
result = 0
number = 0
sign = 1
} else if (s[i] == ')') {
// Finish calculating the result before ')'
result += number * sign
// Calculate the previous result (before parenthese) and the result inside the parenthese
// Stack order: previous result, sign before parenthese
val previousSign = stack.pop() // It will be the sign before the parenthese, i.e. 1
val previousResult = stack.pop() // It's previous result calculated before the parenthese, i.e. 10
result = previousResult + previousSign * result
// Reset all state
number = 0
sign = 1
// Or equivalently
// result *= stack.pop() // It will be the sign before the parenthese, i.e. -
// result += stack.pop() // It's previous result calculated before the parenthese, i.e. 10
} else if (s[i] == '+') {
result += number * sign
sign = 1
number = 0
} else if (s[i] == '-') {
result += number * sign
sign = -1
number = 0
}
}
// We calculate the remaining number, from above example, it ..)-5
if (number != 0) result += number * sign
return result
}
// Or equivalently, we sum up the result when we finish parsing the number
fun calculate(s: String): Int {
val stack = Stack<Int>() // Stack to store previous results
var result = 0 // Running total
var sign = 1 // Current sign (+1 or -1)
var i = 0
val n = s.length
while (i < n) {
when (s[i]) {
' ' -> {} // Ignore spaces
'+' -> sign = 1
'-' -> sign = -1
'(' -> {
stack.push(result) // Save current result
stack.push(sign) // Save current sign
result = 0 // Reset for inner expression
sign = 1 // Reset sign
}
')' -> {
result *= stack.pop() // Apply the saved sign
result += stack.pop() // Add saved result
}
else -> { // A number
var num = 0
while (i < n && s[i].isDigit()) {
num = num * 10 + (s[i] - '0')
i++
}
result += num * sign // Apply sign
i-- // Adjust for loop increment, we increment below
}
}
i++
}
return result
}We can evaluate the expression recursively. We can define a recursive function to evaluate the expression within the parentheses.
TODO: Verify this solution, and try to understand.
fun calculateRecursive(s: String): Int {
var i = 0
fun evaluate(): Int {
var result = 0
var sign = 1
while (i < s.length) {
when (s[i]) {
' ' -> {} // Ignore spaces
'+' -> sign = 1
'-' -> sign = -1
'(' -> {
i++
result += sign * evaluate() // Recursively evaluate
}
')' -> return result // Return when closing `)`
else -> { // Number
var num = 0
while (i < s.length && s[i].isDigit()) {
num = num * 10 + (s[i] - '0')
i++
}
result += sign * num
i-- // Adjust for loop increment
}
}
i++
}
return result
}
return evaluate()
}