Show problems as
Classic problem #772HardMathStringStackRecursion

Basic Calculator III

Real-world version: Till Keypad Expression
Tracked in this browser only
Read Basic Calculator III on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A market-stall till lets the trader type a whole price calculation on the keypad before pressing total. The keystrokes arrive as the string s, which contains decimal digits, the four operator keys +, -, * and /, and the bracket keys ( and ). There are no spaces, every operator sits between two operands, and no number is preceded by a sign.

Work out what the till should display, following these rules:

  • * and / bind more tightly than + and -.
  • Operators that bind equally tightly are applied from left to right, so 60/4/5 is 3.
  • A bracketed section is worked out first and then used as a single operand.
  • / is whole-number division that throws away any fractional part, rounding toward zero. So (0-9)/4 is -2, not -3.
  • No division by zero occurs.

Return the displayed value. Do not pass the string to a built-in expression evaluator.

Examples

Example 1

Input
s = "9+40/6*2"
Output
21

The tighter operators go first: 40/6 discards the remainder and gives 6, then 6*2 is 12, and finally 9+12 is 21.

Example 2

Input
s = "(70-90)/6"
Output
-3

The bracket gives -20, and dividing -20 by 6 rounds the quotient toward zero, so the till shows -3.

Example 3

Input
s = "4*(8+2*(9-6))-50/4"
Output
44

The inner bracket is 9-6 = 3, so 2*3 = 6 and the outer bracket is 8+6 = 14. Then 4*14 = 56, and 50/4 = 12, leaving 56-12 = 44.

Constraints

  • 1 <= s.length <= 10^4
  • s contains only the characters '0'-'9', '+', '-', '*', '/', '(' and ')'.
  • s is a well-formed expression in which every operator is binary.
  • The final value and every value reached along the way lie between -2^31 and 2^31 - 1.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def calculate(s: str) -> int:
Java
public int calculate(String s)

More on the same topics