Leetcode Problem 1597. Build Binary Expression Tree From Infix Expression

1597. Build Binary Expression Tree From Infix Expression

Leetcode Solutions

Two Stacks Infix Expression Parsing

  1. Initialize two stacks: ops for operators and nums for operand nodes.
  2. Iterate over each character in the input string s.
  3. If the character is a digit, create a node and push it onto the nums stack.
  4. If the character is an operator (+, -, *, /): a. While the ops stack is not empty and the top operator has greater or equal precedence, pop the operator from ops and pop two nodes from nums, create a new node with these as children, and push the new node onto nums. b. Push the current operator onto the ops stack.
  5. If the character is an opening parenthesis (, push it onto the ops stack.
  6. If the character is a closing parenthesis ), keep resolving the top operator of the ops stack until an opening parenthesis is encountered.
  7. After the loop, if there are remaining operators in the ops stack, resolve them.
  8. The top node on the nums stack is the root of the binary expression tree.
UML Thumbnail

Recursive Descent Parsing

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...