LeetCode 1597: Build Binary Expression Tree From Infix Expression
Problem Description
Explanation
To build a binary expression tree from an infix expression, we can use the shunting yard algorithm. The shunting yard algorithm converts infix expressions to postfix notation, which can then be used to build the binary expression tree.
The steps involved in the algorithm are as follows:
- Initialize an empty stack for operators (opStack) and an empty list for the postfix expression (postfixList).
- Iterate through the infix expression from left to right:
- If the current token is an operand, add it to the postfix list.
- If the current token is an operator:
- While the opStack is not empty and the precedence of the current token is less than or equal to the precedence of the top of the opStack, pop operators from the opStack and add them to the postfix list.
- Push the current operator onto the opStack.
- After iterating through the infix expression, pop any remaining operators from the opStack and add them to the postfix list.
- Build the binary expression tree from the postfix expression using a stack:
- For each token in the postfix expression:
- If the token is an operand, push it onto the stack.
- If the token is an operator, pop the top two operands from the stack, create a new node with the operator as the value and the two operands as its left and right children, and push this node back onto the stack.
- The final node on the stack is the root of the binary expression tree.
- For each token in the postfix expression:
The time complexity of this algorithm is O(n) where n is the length of the infix expression, and the space complexity is O(n) for the stack and postfix list.
Solutions
class Solution {
public Node expTree(String s) {
Stack<Node> stack = new Stack<>();
Stack<Character> opStack = new Stack<>();
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
stack.push(new Node(c));
} else if (c == '(') {
opStack.push(c);
} else if (c == ')') {
while (!opStack.isEmpty() && opStack.peek() != '(') {
processOperator(stack, opStack.pop());
}
opStack.pop(); // Pop the '('
} else if (isOperator(c)) {
while (!opStack.isEmpty() && precedence(opStack.peek()) >= precedence(c)) {
processOperator(stack, opStack.pop());
}
opStack.push(c);
}
}
while (!opStack.isEmpty()) {
processOperator(stack, opStack.pop());
}
return stack.pop();
}
private boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
private int precedence(char op) {
if (op == '+' || op == '-') {
return 1;
} else if (op == '*' || op == '/') {
return 2;
}
return 0;
}
private void processOperator(Stack<Node> stack, char op) {
Node right = stack.pop();
Node left = stack.pop();
Node newNode = new Node(op);
newNode.left = left;
newNode.right = right;
stack.push(newNode);
}
}Loading editor...