Key takeaways:
Calculates complex expressions by parsing digits, operators, and parentheses.
Uses stack-based handling to manage sign context in nested expressions.
Efficiently evaluates expressions with
time and space complexity.
Imagine you’re developing a calculator application that allows users to input complex arithmetic expressions for evaluation. A user, Sarah, inputs the expression
Ensuring accurate evaluation of arithmetic expressions is crucial for calculator applications like yours. Users rely on these tools for precise calculations in various fields, including education, finance, and engineering. By correctly interpreting parentheses, handling multi-digit integers, and respecting operator precedence, your calculator can provide Sarah with reliable results, enhancing her trust in your application.
Given a string s
, representing a valid arithmetic expression, your task is to implement a basic calculator to evaluate the expression and return the result. The expression will contain non-negative integers, plus (+), minus (-), parenthesis, and spaces.
The program should be able to handle multi-digit integers, properly interpret parentheses to determine the order of operations, and account for positive and negative signs within the expressions.
Let’s test your understanding of the problem.
What should be the output of the expression ?
6
5
7
8
To efficiently evaluate arithmetic expressions provided as strings, we adopt a stack-based approach combined with iterative parsing of the input expression. The main idea is to traverse the expression character by character, appropriately handling digits, operators, and parentheses to compute the final result.
Initialization: We initialize several variables, including cur
to track the current operand being processed, res
to store the running total of the expression, sign
to represent the current sign and stack
to maintain the sign context within parentheses.
Iterative parsing: We iterate through each character of the input expression. Depending on the type of character encountered (digit, operator, or parenthesis), we perform specific operations, such as updating the current operand cur
, adjusting the current sign sign
, or manipulating the stack to handle parentheses.
Operand and operator handling: When encountering digits, we appropriately combine them to form multi-digit operands. For operators (+, -), we update the result res
based on the current operand cur
and sign sign
, and reset cur
to 0 to prepare for the next operand.
Parentheses handling: We utilize a stack to keep track of the sign context within parentheses. When an opening parenthesis is encountered, we push the current sign onto the stack. Upon encountering a closing parenthesis, we pop the top sign from the stack to restore the sign context.
Final result calculation: After parsing the entire expression, we add the final operand cur
multiplied by the final sign sign
to the running total res
, yielding the ultimate result of the arithmetic expression.
By employing this approach, we ensure accurate evaluation of arithmetic expressions while maintaining efficiency in terms of time and space complexity. Additionally, this method effectively handles complex expressions with nested parentheses and multi-digit operands.
Let’s code our approach in Python, C++, C#, Java, JavaScript, and Go.
def calculate(s):# Define and initialize parameterscur = 0res = 0sign = 1stack = [sign]# Iterate through the stringfor c in s:# If current character is a digitif c.isdigit():cur = cur * 10 + int(c)# If current character is an opening paranthesiselif c == '(':stack.append(sign)# If current character is a closing paranthesiselif c == ')':stack.pop()# If current character is an + or - signelif c == '+' or c == '-':res += sign * curif c == '+':sign = 1 * stack[-1]elif c == '-':sign = -1 * stack[-1]cur = 0return res + sign * cur# Test casesexp1 = "1 + 1"exp2 = " 2-1 + 2 "exp3 = "(1+(4+5+2)-3)+(6+8)"print("The answer for the expression", exp1, "is:", calculate(exp1)) # 2print("The answer for the expression", exp2, "is:", calculate(exp2)) # 3print("The answer for the expression", exp3, "is:", calculate(exp3)) # 23
In the above code in Python:
Line 1: We initialize the calculate
function, which takes a string s
as input.
Line 3: cur
is initialized to 0 to track the current number being formed.
Line 4: res
is initialized to 0, used to store the running result.
Line 5: sign
is set to 1, representing the current number’s sign (positive or negative).
Line 6: stack
is initialized with sign
, used to handle signs within parentheses.
Line 8: We start iterating through each character c
in the string s
.
Line 10: Checks if c
is a digit.
Line 11: If it is, updates cur
by multiplying its current value by 10 (to shift left) and adding the integer value of c
.
Line 13: Checks if c
is an opening parenthesis '('
.
Line 14: If it is, pushes sign
onto stack
to save the current context.
Line 16: Checks if c
is a closing parenthesis ')'
.
Line 17: If it is, pops the top value from stack
to restore the previous sign context.
Line 19: Checks if c
is either '+'
or '-'
.
Line 20: If it is, adds cur * sign
to res
(updating the result with the last number and its sign).
Lines 21–22: If c
is '+'
, sets sign
to 1 * stack[-1]
to keep the sign positive.
Lines 23–24: If c
is '-'
, sets sign
to -1 * stack[-1]
to set the sign as negative.
Line 25: This resets cur
to 0 to start capturing the next number.
Line 26: After the loop, adds the final cur * sign
to res
, ensuring the last number is included in the result and returns res
as the calculated result of the expression.
The time complexity of the provided code is s
. This is because the code iterates through each character of the input string exactly once to evaluate the arithmetic expression.
The space complexity is s
. The space usage primarily comes from the stack
data structure, which can grow up to the size of the input string in the worst-case scenario where every character is an opening parenthesis.
Free Resources