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.