227. Basic Calculator II

Problem Statement

link: https://leetcode.com/problems/basic-calculator-ii/ https://leetcode.cn/problems/basic-calculator-ii/

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:

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

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

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

Solution Approach

The approach involves using a stack to keep track of numbers and operators while iterating through the input string, performing the necessary calculations for addition, subtraction, multiplication, and division.

Algorithm

1. Initialize an empty stack, a variable cur for the current number, and op for the current operator (initialized to ‘+’).
2. Iterate through the input string, updating cur for digits, performing operations when an operator is encountered, and pushing results onto the stack.
3. After the loop, sum the elements in the stack to obtain the final result and return it as the evaluated expression value.

Implement

    class Solution:
    def calculate(self, s: str) -> int:
        stack, cur, op = [], 0, '+'
        for c in s + '+':
            if c == " ":
                continue
            if c.isdigit():
                cur = (cur * 10) + int(c)
            else:
                if op == '-':
                    stack.append(-cur)
                elif op == '+':
                    stack.append(cur)
                elif op == '*':
                    stack.append(stack.pop() * cur)
                elif op == '/':
                    stack.append(int(stack.pop()/cur))
                cur, op = 0, c
        return sum(stack)

 

    
    

Twitter  facebook  Email