Design an object-oriented basic calculator that evaluates a valid arithmetic expression provided as a string.

The expression may contain integers, addition, subtraction, parentheses, and spaces. Parenthesized expressions must be evaluated before the surrounding expression.

Class

BasicCalculator

Constructor

BasicCalculator

BasicCalculator()

• Creates a calculator that can evaluate arithmetic expressions.

Method

calculate

int calculate(String expression)

• Evaluates the non-null valid arithmetic expression expression.
• Returns the integer result.

Expression Rules

• expression contains digits, spaces, +, -, (, and ).
• Integer literals contain one or more digits and are non-negative.
• The - operator may be used as either binary subtraction or unary negation.
• Unary negation may appear at the beginning of an expression or a parenthesized expression.
• The + operator is never used as a unary operator.
• Two operators never appear consecutively.
• All parentheses are correctly matched.
• Addition and subtraction at the same parenthesis level are evaluated from left to right.
• Spaces do not affect the result.
• Each call to calculate is independent of all previous calls.
• Built-in expression evaluators such as eval must not be used.

Object-Oriented Design

• Use objects with clear responsibilities for parsing and evaluating expressions.
• Private helper classes or interfaces may be added for numbers, operations, or expression components.
• The required public class and method signature must remain exactly as specified.

Constraints

• 1 ≤ expression.length() ≤ 300,000
• expression is a valid, non-null expression.
• Every integer and intermediate result fits within the signed 32-bit integer range.
• The final result is between -2,147,483,648 and 2,147,483,647, inclusive.

Expected Efficiency

• Evaluating an expression of length n should take O(n) time.
• The solution may use O(n) additional space.

Example 1

calculate(expression = "18 - (7 + 4) + 3")

Output: 10

The parenthesized expression equals 11, so the result is 18 - 11 + 3 = 10.

Example 2

calculate(expression = "-(12 - (5 + 2)) + 9")

Output: 4

The nested sum is 7, so the negated parenthesized value is -(12 - 7) = -5. Adding 9 gives 4.

Example 3

calculate(expression = "50 - (20 - (6 - 9))")

Output: 27

The innermost expression is -3. Therefore, 20 - (-3) = 23 and 50 - 23 = 27.

Example 4

calculate(expression = "7 - (-(3 + 2))")

Output: 12

The parenthesized sum is negated to -5, so the final result is 7 - (-5) = 12.