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.

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.

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. 

infix expression to construct binary expression tree

July 13, 2018

Introduction

It is my favorite thing to do to scan the code qucikly in less than 15 minutes. Here is C++ for the algorithm.

Using stack

The really important tips are to use stack, so the time complexity can be implemented using O(n) time to parse the infix expression. And the binary express tree can be built in bottom up way. The similar idea using stack can be see in multiple places.

The ) bracket is used to determine when to pop the stack and handle the operand and also operator.


Here is the gist I created how to use stack to parse the infix expression and then construct the binary expression tree.

Here is the output of stack working on a simple test case:

My bet was wrong

 I knew that stack is used on reverse polish notation. And it is widely used to parse the input. There is a hard level algorithm Leetcode 301 to parse parentheses, I did write 10 blogs on that. I also did work on hard level algorithm using more than 10 ideas.

 But the performance on 30 minutes is beyond my control. I could not think clearly using stack and stop on close bracket ), and then start to pop and then construct binary express tree from bottom up.

 What I did is to think about finding operator (1 + 2) so that I can use the string manipulation to get the result. I am not aiming highest potential I can reach in those 30 minutes.

 Through the performance, I understood that it is very important for me to calm down, and list all the options I have. Stack or not using stack, what is time complexity? Can I beat other people to write an optimal time complexity solution.

 I still remembered that I practiced a hard level algorithm on hackerrank and learn the power of using stack. The algorithm is called Reverse shuffle merge.

Actionable Items

Review all past practice using stack.

Here is the first one, Leetcode 109: convert sorted list to binary search tree.

Review one of solution using O(n) time O(1) space, the link is here.

Follow up

Most important is to understand the space is cheap, using space to expedite the time is always best choice, need to scale the problem in large expression. This time I failed to give it a try in 30 minutes using stack to get linear time complexity.