Problem Link - Transform the Expression
Problem Statement
Reverse Polish Notation (RPN) is a mathematical notation where every operator follows all of its operands. For instance, to add three and four, one would write “3 4 +” rather than “3 + 4”. If there are multiple operations, the operator is given immediately after its second operand; so the expression written “3 − 4 + 5” would be written “3 4 − 5 +” first subtract 4 from 3, then add 5 to that.
Transform the algebraic expression with brackets into RPN form.
Approach
The code uses a stack to manage operators and parentheses. Whenever a lowercase letter is encountered, it is added to the result directly. For opening parentheses, they are pushed onto the stack, while for closing parentheses, the code pops elements from the stack until it finds the corresponding opening parenthesis.
Since the problem specifies only single-letter variables and does not mention operators, the code effectively ignores operator handling beyond managing parentheses. This logic ensures that the output follows RPN format.
Time Complexity
The time complexity of this solution is O(n), where n is the length of the expression.
Space Complexity
The space complexity is O(n) in the worst case, primarily due to the stack that can hold all operators and parentheses.