Evaluate Infix Expression (Shunting-Yard)

Problem Description

Given a valid infix arithmetic expression containing non-negative integers, parentheses ( ), and the binary operators +, -, *, and /, evaluate the expression and return its result as double data type. Division should truncate toward zero.

Implement the Shunting-Yard algorithm to first convert the infix expression to Reverse Polish Notation (postfix), then evaluate the postfix expression.

---

Input Format

A single line containing the infix expression string s.

• s consists of digits (0–9), spaces, parentheses ( and ), and operators +, -, *, /.
• Operands and operators may be separated by one or more spaces.

Output Format

Double (data type) representing the evaluated result of the expression.

---

Constraints

• 1 <= s.length <= 10^5
• The expression is guaranteed to be valid.
• Intermediate results and the final result fit into a 32-bit signed integer.

---

Examples

Example	Input	Output	Explanation
1	3 + 2 * 2	7	2*2 = 4, then 3+4 = 7
2	3/2	1	3/2 truncated toward zero yields 1
3	(1+(4+5+2)-3)+(6+8)	23	Evaluate inner parentheses step by step

---

Topics

• Stack
• String Parsing
• Shunting-Yard Algorithm
• Reverse Polish Notation (RPN)
• Expression Evaluation

---