Problem Link - Evaluate Expression
Problem Statement -
You are given a string SS consisting of NN characters. Each character is either a digit from 00 to 99 or an operator out of +, -, and *.
Consider the string to be in reverse polish notation consisting of digits (from 11 to 99) as the operands and +, -, or * as the operators and evaluate the expression.
Approach:
The key idea is to use a stack to perform the calculations based on the operators encountered:
-
Stack Initialization: A stack is created to hold numbers as we process the expression.
-
Processing the Expression: The code iterates through each character in the input string:
-
If the character is a digit (0-9), it is converted from a character to an integer and pushed onto the stack.
-
If the character is an operator (
+,-,*,/), the two top numbers are popped from the stack, the operation is performed, and the result is pushed back onto the stack.
-
-
Handling Operators: Each operator works as follows:
-
For
+, pop the top two numbers, add them, and push the result. -
For
-, pop the top two numbers, subtract the first popped number from the second, and push the result. -
For
*, pop the top two numbers, multiply them, and push the result. -
For
/, pop the top two numbers, divide the second popped number by the first, and push the result.
-
-
Final Result: After processing the entire expression, the final result is at the top of the stack.
Time Complexity:
O(n), where n is the number of characters in the input expression, as each character is processed once.
Space Complexity:
O(n), since the stack may store all numbers until the final result is computed.