Infix expression to a binary expression tree

July 14, 2018

Introduction

It is the second meeting with a peer after six months. We met together this January 2018. And then I gave him the algorithm to work on which is to construct binary expression tree using infix expression.

Problem solving

The peer is very strong at coding skills, so he chose the optimal solution linear time O(N), and tried very hard to figure out how to design parsing algorithm using stack.

Here is the transcript how he approached the problem. I can tell that he is very smart on time complexity compared to me.

	convert infix expression to binary expression tree
	for example, ((2 + 2)+3)
	The solution written by the peer:
	+
	+ 3
	1 2
	stack (
	+
	+ 3
	1 2
	((1+2)+3)
	+
	+ 3
	1 2
	class Solution {
	class Node {
	public String value;
	public Node left, right;
	public Node(String value) {
	this.value = value;
	}
	}
	public Node convert(String s) {
	int n = s.length();
	if (n == 0) return null;
	Deque<Node> stack = new LinkedList<>();
	stack.addLast(new Node('+'));
	for(int i = 1; i < n; i++) {
	char ch = s.charAt(i);
	if (ch == '(' || Character.isDigit(ch)) {
	Node newNode = new Node(ch == '(' ? "+" : ch);
	Node node = stack.peekLast();
	if (node.left == null) node.left = newNode;
	else if (node.right == null) node.right = newNode;
	stack.addLast(newNode);
	}
	}
	}
	}
	}

view raw using infix Expression to construct binary expression tree hosted with ❤ by GitHub

My feedback

The peer did very good to find optimal solution, try to use stack to parse the string once and build a binary expression tree. The time complexity is O(N), N is length of infix expression. And the peer communicated very well, there are multiple solutions and he decided to push the number and operator to the stack and also build a binary tree node in the same time. Somehow he should think about validation of expression string, and also try to simplify the code. 

Here is my feedback gist.

	use infix expresssion to construct binary expression tree
	My feedback after the performance of 30 minutes of the peer:
	Leet us to work on a simple infix expression and see how we can solve the problem together.
	Given infix expression (1+2), we like to use stack to construct the binary expression tree.
	First all elements in the expression are pushed to the stack until close bracket is met.
	Here are the steps:
	infix expression: (1+2)
	create a stack,
	( -> to the stack
	1 -> to the stack
	+ -> to the stack
	2 -> to the stack
	------), we need to pop stack four times to get two operands, one operator, one open bracket.
	let get number operand 1 : 2
	get operator : +
	get operand : 1
	get open brakcet ( - match - expression is wrong
	And then a binary tree construction here:
	you can do - create a node for +
	put left child and right child to +
	put node for another stack for binary tree stack -> bottom up
	() out of control to help you to parse ->
	four operations ->
	Similar algorithms to relate to:
	Leetcode 301 - > () bracket, invalid bracket, I studied over 10 solutions ->
	Need to write something for 30 minutes performance
	The peer said that he may fail because he could not write a completed solution. Even though he has optimal solution based on
	time complexity and also use stack - know how to use data structure to get optimal time complexity.
	Detail cannot be finalized in 30 minutes time range.

view raw use infix expression to construct a binary express tree hosted with ❤ by GitHub

Statistics

Meeting time July 14, 2018 9:00 AM PST - 11:10 AM PST

First the peer worked on the infix expression to binary expression tree, and then I worked on the two algorithms, discussion of "Find a path with minimum maximum value in the matrix".

Follow up 

July 16, 2018


I wrote C# code to implement the algorithm using O(N) time complexity, N is the expression length.