Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

LeetCode 227: Basic Calculator II

By Duncan Smith Jan 13 0

LeetCode 2021

Problem

LeetCode 227: Basic Calculator II (Medium)

Problem statement: Evaluate a valid arithmetic expression containing only numbers, spaces, and the operators +, -, *, and /.

This is almost as simple as an arithmetic expression evaluator can be. It’s simpler than the first Basic Calculator problem, which includes parentheses. The only trick in this version is respecting the order of operations, which in this case is just MDAS since there are no parentheses or exponents.

This solution variation doesn’t use a stack, so it relies on processing the input string character by character (one pass) and setting each variable at the correct point in the process.

Solution

This solution is based on the official LeetCode solution (available without a subscription), Approach 2: Optimized approach without the stack.

Variables

  • s: The input string
  • i: The position in the input string. We need to know the position because there’s a special case for the last character.
  • c: The current character in the input string. Each character is either a digit or an operator.
  • result: The final result. This variable also stores the intermediate result after an addition or subtraction operation, but is unchanged after a multiplication or division operation.
  • num: An integer operand from the input string.
  • prev: After a multiplication or division operation, this stores the intermediate (previous) result. After an addition or subtraction operation, it is initialized to the current num (or -num) value, so it can be used in an upcoming multiplication or division.
  • op: The most recent operator, set at the end of the previous iteration. It is initialized to +, since the first operand is always positive.

Algorithm

  • Remove all spaces from the input string s, so the only remaining characters are digits and operators.
  • Process each character c of s.
  • If c is a digit, append it to the current integer operand, num.
  • If c is not a digit or c is the last character in s, do the steps below. The “last character” special case is required because the input string doesn’t contain an “evaluate expression” operator like =.

Evaluation steps:

  • op always contains the current operator: + when the program starts, or the most recent operator seen in the input.
  • If op is + or -, add prev to result. This is equivalent to popping any pending multiplication or division operation in the stack version of this algorithm. Then set prev to num if op is + or -num if op is -. This sets the intermediate result that any future operations will operate on.
  • If op is *, multiply prev (the intermediate result) by num (the next operand).
  • If op is /, divide prev (the intermediate result) by num (the next operand).
  • Set op (the next operation) to c.
  • Set num to 0 so we start with a fresh number when we encounter the next digit.

Pseudocode

remove all spaces from s
for each char c in input string
    if c is a digit, append it to num
    if c is not a digit or c is the last character in s
        if op is + or -
            add prev to result
            if op is +, set prev to num
            else set prev to -num
        if op is *, multiply prev by num
        if op is /, divide prev by num
        op = c
        num = 0
add prev to result
return result

Code

Basic Calculator II on GitHub.

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

Categories: LeetCode

Prev
Next

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • 2023 in Review: 50 LeetCode Tips
  • 2022 in Review: Content Bots
  • 2021 in Review: Thoughts on Solving Programming Puzzles
  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • Do Coding Bots Mean the End of Coding Interviews? December 31, 2024
  • Another Project for 2024 May 8, 2024
  • Dynamic Programming Wrap-Up May 1, 2024
  • LeetCode 91: Decode Ways April 24, 2024
  • LeetCode 70: Climbing Stairs April 17, 2024
  • LeetCode 221: Maximal Square April 10, 2024
  • Using Dynamic Programming for Maximum Product Subarray April 3, 2024
  • LeetCode 62: Unique Paths March 27, 2024
  • LeetCode 416: Partition Equal Subset Sum March 20, 2024
  • LeetCode 1143: Longest Common Subsequence March 13, 2024
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2025 Duncan Smith