# Basic Calculator II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/basic-calculator-ii)
Canonical: https://scaleengineer.com/dsa/problems/basic-calculator-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String, Stack
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Airbnb](https://scaleengineer.com/companies/airbnb), [ByteDance](https://scaleengineer.com/companies/bytedance), [DoorDash](https://scaleengineer.com/companies/doordash), [Google](https://scaleengineer.com/companies/google), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Snowflake](https://scaleengineer.com/companies/snowflake), [Zoho](https://scaleengineer.com/companies/zoho), [Coupang](https://scaleengineer.com/companies/coupang), [Tesla](https://scaleengineer.com/companies/tesla), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Snap](https://scaleengineer.com/companies/snap), [Zoox](https://scaleengineer.com/companies/zoox), [Anduril](https://scaleengineer.com/companies/anduril), [IXL](https://scaleengineer.com/companies/ixl), [NetApp](https://scaleengineer.com/companies/netapp), [Verkada](https://scaleengineer.com/companies/verkada), [The Trade Desk](https://scaleengineer.com/companies/the-trade-desk), [Highspot](https://scaleengineer.com/companies/highspot), [Rokt](https://scaleengineer.com/companies/rokt)
---
## Problem
Given a string `s` which represents an expression, _evaluate this expression and return its value_. 

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of `[-231, 231 - 1]`.

**Note:** You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as `eval()`.

**Example 1:**

**Input:** s = "3+2*2"
**Output:** 7

**Example 2:**

**Input:** s = " 3/2 "
**Output:** 1

**Example 3:**

**Input:** s = " 3+5 / 2 "
**Output:** 5

**Constraints:**

* `1 <= s.length <= 3 * 105`
* `s` consists of integers and operators `('+', '-', '*', '/')` separated by some number of spaces.
* `s` represents **a valid expression**.
* All the integers in the expression are non-negative integers in the range `[0, 231 - 1]`.
* The answer is **guaranteed** to fit in a **32-bit integer**.

# Approaches
## Stack-based Approach with Two Passes
This approach uses a stack to evaluate the expression in two passes. In the first pass, we handle multiplication and division operations, and in the second pass, we handle addition and subtraction.
**Time:** O(n) where n is the length of the input string - we need to traverse the string once · **Space:** O(n) where n is the length of the input string - in worst case, all numbers could be pushed to stack
**Pros:** Easy to understand and implement; Can handle expressions with spaces; Processes operations in correct order of precedence
**Cons:** Uses extra space for stack; Makes two passes through the data (one implicit in summing stack); Not easily extensible for more operators or different precedence rules
### Explanation
The idea is to process the expression in two steps:

1. First pass: Process multiplication and division operations
- Iterate through the string character by character
- Keep track of current number and last operation
- When encountering an operator or end of string:
  - If previous operation was multiplication, multiply with stack top
  - If previous operation was division, divide with stack top
  - For addition/subtraction, push number to stack

2. Second pass: Process addition and subtraction
- Sum up all numbers in the stack considering their signs

Here's the implementation:

```java
public int calculate(String s) {
    Stack<Integer> stack = new Stack<>();
    char lastOp = '+';
    int num = 0;
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        
        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');
        }
        
        if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
            if (lastOp == '+') {
                stack.push(num);
            } else if (lastOp == '-') {
                stack.push(-num);
            } else if (lastOp == '*') {
                stack.push(stack.pop() * num);
            } else if (lastOp == '/') {
                stack.push(stack.pop() / num);
            }
            lastOp = c;
            num = 0;
        }
    }
    
    int result = 0;
    while (!stack.isEmpty()) {
        result += stack.pop();
    }
    return result;
}
```
### Algorithm
1. Initialize a stack and variables for lastOperation and currentNumber
2. Iterate through each character in the string
3. If character is digit, build the number
4. If character is operator or last character:
   - Process previous operation
   - Update lastOperation
5. After processing all characters, sum up the stack

## Single Pass Approach without Stack
This approach processes the expression in a single pass while maintaining only the necessary variables to track the current state and previous values. It doesn't use any additional data structures like a stack.
**Time:** O(n) where n is the length of the input string - we only need one pass through the string · **Space:** O(1) - only uses a constant amount of extra space regardless of input size
**Pros:** Single pass through the input; Constant extra space; More efficient than stack-based approach; Handles operator precedence correctly
**Cons:** Slightly more complex logic; Less intuitive than stack-based approach; Harder to modify for additional operators or different precedence rules
### Explanation
The idea is to keep track of the last calculated number and the current number being processed. We only need to store the previous number when we encounter multiplication or division.

Here's the implementation:

```java
public int calculate(String s) {
    int length = s.length();
    int currentNumber = 0;
    int lastNumber = 0;
    int result = 0;
    char operation = '+';
    
    for (int i = 0; i < length; i++) {
        char currentChar = s.charAt(i);
        
        if (Character.isDigit(currentChar)) {
            currentNumber = (currentNumber * 10) + (currentChar - '0');
        }
        
        if (!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar) || i == length - 1) {
            if (operation == '+' || operation == '-') {
                result += lastNumber;
                lastNumber = (operation == '+') ? currentNumber : -currentNumber;
            } else if (operation == '*') {
                lastNumber = lastNumber * currentNumber;
            } else if (operation == '/') {
                lastNumber = lastNumber / currentNumber;
            }
            operation = currentChar;
            currentNumber = 0;
        }
    }
    
    result += lastNumber;
    return result;
}
```
### Algorithm
1. Initialize variables for result, currentNumber, lastNumber, and operation
2. Iterate through the string once
3. Build numbers when digits are encountered
4. When operator is encountered:
   - For +/-, add lastNumber to result and update lastNumber
   - For */,  perform operation on lastNumber
5. Return result + lastNumber

# Solutions
### CSharp

```csharp
using System.Collections.Generic ; using System.Linq ; struct Element { public char Op ; public int Number ; public Element ( char op , int number ) { Op = op ; Number = number ; } } public class Solution { public int Calculate ( string s ) { var stack = new Stack < Element >(); var readingNumber = false ; var number = 0 ; var op = '+' ; foreach ( var ch in (( IEnumerable < char >) s ). Concat ( Enumerable . Repeat ( '+' , 1 ))) { if ( ch >= '0' && ch <= '9' ) { if (! readingNumber ) { readingNumber = true ; number = 0 ; } number = ( number * 10 ) + ( ch - '0' ); } else if ( ch != ' ' ) { readingNumber = false ; if ( op == '+' || op == '-' ) { if ( stack . Count == 2 ) { var prev = stack . Pop (); var first = stack . Pop (); if ( prev . Op == '+' ) { stack . Push ( new Element ( first . Op , first . Number + prev . Number )); } else // '-' { stack . Push ( new Element ( first . Op , first . Number - prev . Number )); } } stack . Push ( new Element ( op , number )); } else { var prev = stack . Pop (); if ( op == '*' ) { stack . Push ( new Element ( prev . Op , prev . Number * number )); } else // '/' { stack . Push ( new Element ( prev . Op , prev . Number / number )); } } op = ch ; } } if ( stack . Count == 2 ) { var second = stack . Pop (); var first = stack . Pop (); if ( second . Op == '+' ) { stack . Push ( new Element ( first . Op , first . Number + second . Number )); } else // '-' { stack . Push ( new Element ( first . Op , first . Number - second . Number )); } } return stack . Peek (). Number ; } }
```

### Java

```java
class Solution { public int calculate ( String s ) { Deque < Integer > stk = new ArrayDeque <>(); char sign = '+' ; int v = 0 ; for ( int i = 0 ; i < s . length (); ++ i ) { char c = s . charAt ( i ); if ( Character . isDigit ( c )) { v = v * 10 + ( c - '0' ); } if ( i == s . length () - 1 || c == '+' || c == '-' || c == '*' || c == '/' ) { if ( sign == '+' ) { stk . push ( v ); } else if ( sign == '-' ) { stk . push (- v ); } else if ( sign == '*' ) { stk . push ( stk . pop () * v ); } else { stk . push ( stk . pop () / v ); } sign = c ; v = 0 ; } } int ans = 0 ; while (! stk . isEmpty ()) { ans += stk . pop (); } return ans ; } }
```

### CPP

```cpp
class Solution { public: int calculate ( string s ) { int v = 0 , n = s . size (); char sign = '+' ; stack < int > stk ; for ( int i = 0 ; i < n ; ++ i ) { char c = s [ i ]; if ( isdigit ( c )) v = v * 10 + ( c - '0' ); if ( i == n - 1 || c == '+' || c == '-' || c == '*' || c == '/' ) { if ( sign == '+' ) stk . push ( v ); else if ( sign == '-' ) stk . push ( - v ); else if ( sign == '*' ) { int t = stk . top (); stk . pop (); stk . push ( t * v ); } else { int t = stk . top (); stk . pop (); stk . push ( t / v ); } sign = c ; v = 0 ; } } int ans = 0 ; while ( ! stk . empty ()) { ans += stk . top (); stk . pop (); } return ans ; } };
```

### Python

```python
class Solution : def calculate ( self , s : str ) -> int : v , n = 0 , len ( s ) sign = '+' stk = [] for i , c in enumerate ( s ): if c . isdigit (): v = v * 10 + int ( c ) if i == n - 1 or c in '+-*/' : if sign == '+' : stk . append ( v ) # for "10-2*5": when '-' encountered, var 'sign' is still '+' # so '10' will be pushed to stk before setting sign to '-' elif sign == '-' : stk . append ( - v ) elif sign == '*' : stk . append ( stk . pop () * v ) elif sign == '/' : stk . append ( int ( stk . pop () / v )) else : print ( "operator not supported" ) sign = c # reset inside 'if' v = 0 return sum ( stk )
```