Basic Calculator Iv - Leetcode Solution

Problem Statement:

Design a basic calculator that can evaluate a simple arithmetic expression consisting of only multiplication, division, and addition and subtraction operators. The expression contains integers and the +, -, *, / operators, represented as a string.

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

Example 1: Input: "3+2*2" Output: 7

Example 2: Input: " 3/2 " Output: 1

Example 3: Input: " 3+5 / 2 " Output: 5

Solution:

To solve this problem, we need to evaluate the given arithmetic expression. We can do this using a stack data structure. The idea is to read the input string one character at a time and build the stack. If the current character is a number, we keep reading until we hit an operator, then push the number onto the stack. If the current character is an operator, we pop the top two elements, and apply the operator to them then push the result back onto the stack. Once we reach the end of the expression string, we simply return the top element of the stack.

Algorithm:

1. Initialize an empty stack.
2. Initialize a variable "num" to 0.
3. Initialize a variable "operator" to "+".
4. Parse the input string one character at a time: a. If the current character is a digit, continue reading until we hit an operator or the end of the string. Convert the string of digits to an integer, then push it to the stack. b. If the current character is an operator: i. If the operator is "+" or "-", the current "num" is complete. Apply the operator to the previous "num" and push the result to the stack. ii. If the operator is "*" or "/", pop the top element from the stack and apply the operator to the current "num" and the popped element. Then push the result to the stack. c. Update the "num" variable to the next number in the string. d. Update the "operator" variable to the next operator in the string.
5. Once the end of the string is reached, the final result is the top element of the stack.

Code:

class Solution: def calculate(self, s: str) -> int: stack = [] num = 0 operator = "+" for i in range(len(s)): if s[i].isdigit(): num = num * 10 + int(s[i]) if ((not s[i].isdigit()) and (not s[i].isspace())) or i == len(s) - 1: if operator == "-": stack.append(-num) elif operator == "+": stack.append(num) elif operator == "*": stack.append(stack.pop() * num) else: stack.append(int(stack.pop() / num)) operator = s[i] num = 0 return sum(stack)

1