-
Couldn't load subscription status.
- Fork 135
Description
Problem:
In Problem 7 of the Stacks Series (Leetcode 227: Basic Calculator II), the current two-stack C++ implementation returns an incorrect result for valid expressions involving only + and - due to how we are handling the order of operations for + and - in the final loop.
The following test case fails for the Approach using two stacks:
Input: "1-1+1"
Expected Output: 1
Actual Output: -1
Root Cause:
In the current implementation, the remaining operators (+, -) are applied in reverse order after parsing is complete. However, these operators are left-associative and should be applied in left-to-right order. For example:
1 - 1 + 1 // should be read as: (1 - 1) + 1 = 1
// The existing code evaluates as:
1 - (1 + 1) = -1Fix Summary:
To keep changes minimal and fixing the issue, we reverse the numbers and operators stacks into numRev and opRev and apply remaining + and - operators in left-to-right order.
Language / File Affected:
C++ – basic-calculator-ii.md
Validation:
I verified this test case on LeetCode and confirmed that the expected output is correct.
Leetcode Accepted Solution
Updated the basic-calculator-ii.md C++ solution to reflect this fix, PR-11