567. Convert Infix to Postfix

Given a valid infix expression string s with single-character operands (letters or digits), the binary operators + - * / ^ (with ^ right-associative and standard precedence ^ > * / > + -), and parentheses, convert it to its postfix (Reverse Polish) form and return it as a string with no separators. The input is JSON {s}.

Input: JSON {s}.

Output: String — the postfix expression.

Examples

Input: {"s":"a+b*c"}
Output: abc*+
Explanation: Multiplication binds tighter than addition.

Input: {"s":"(a+b)*c"}
Output: ab+c*
Explanation: Parentheses force the addition first.

Input: {"s":"a^b^c"}
Output: abc^^
Explanation: Exponent is right-associative.

Constraints

• 1<=|s|<=10^4
• valid infix

Asked by