930. Infix to Postfix Conversion
You are given a string expression representing a valid infix mathematical expression. Your task is to convert this expression into its equivalent postfix notation, also known as Reverse Polish Notation (RPN).
The expression may include:
- Operands: single lowercase English letters (a to z) or single-digit numbers (0 to 9)
- Binary operators: +, -, *, /, ^
- Parentheses: ( and ) to indicate grouping and precedence
Operator precedence (from highest to lowest):
- ^ (exponentiation)
- *, / (multiplication and division)
- +, - (addition and subtraction)
Associativity:
- ^ is right-associative
- All other operators are left-associative
- Parentheses override standard precedence
You must return the corresponding postfix expression as a string.
The result must not contain any spaces or separators between characters.
Example 1:
Input: expression = "a+b*c"
Output: "abc*+"
Explanation:
Multiplication has higher precedence than addition, so b * c is evaluated first, then added to a.
Example 2:
Input: expression = "(a+b)*c"
Output: "ab+c*"
Explanation:
The parentheses ensure that a + b is evaluated before multiplying with c.
Now Your Turn!
Pick the correct output for the given inputInput: expression = "a+b*c^d-e^f*g+h"
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= expression.length <= 104
- The expression is syntactically valid and properly parenthesized
- Operands are always single characters
- No whitespace appears in the input or output
- All operators are binary