Use Infix expression to construct a binary expression tree

Question

Problem statement

Construct a binary expression using infix expression. The infix expression uses extra parenthesis to enforce the priority of operators.

For example, infix expression ((1+2)+3) can be expressed in a binary expression tree in the following:
+
/ \
+ 3
/ \
1 2

Write down your assumptions in your code. Sometimes comment is also helpful for people to evaluate how good you are in terms of problem solving skills.

My introduction

It is very good algorithm to learn to use stack to parse the expression, even though it is not straightforward. In order to get optimal time complexity, linear time by scanning the infix expression once, using data structure stack.

The challenge is to write a solution in less than 30 minutes, and also show good design of object-oriented programming.

The infix expression is enforced to use extra open and close parenthesis. For example, (1 + 2) should be valid expression and then char '(' defines the start of a new expression. One idea is to linear scan the expression, push '(' into stack, and then '1' into stack, and then '+' into stack, '2' into stack, and then once ')' is visited, then pop up stack for 2 operands one operator and one '(' char to construct a binary tree using operator as the root.

Here is my C# code, please help me to review my solution.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace infixExpressionToBinaryExpressionTree
{
 class Program
 {
 internal class Node
 {
 public char Operand { get; set; } // operator sometimes;
 public Node Left;
 public Node Right;
 public Node(char val)
 {
 Operand = val;
 }
 }
 static void Main(string[] args)
 {
 //RunTestcase1();
 RunTestcase2();
 }
 public static void RunTestcase1()
 {
 var node = InfixExpressionToBinaryExpressionTree("(1+2)");
 Debug.Assert(node.Operand == '+');
 }
 public static void RunTestcase2()
 {
 var node = InfixExpressionToBinaryExpressionTree("((1+2)*(3-4))");
 Debug.Assert(node.Operand.CompareTo("*") == 0);
 }
 public static string Operators = "+-*/";
 public static string Operands = "0123456789"; // make it simple, one digit only first
 /// <summary>
 /// Time complexity: O(N), space complexity: using stack -> at most O(N)
 /// </summary>
 /// <param name="expression"></param>
 /// <returns></returns>
 public static Node InfixExpressionToBinaryExpressionTree(string expression)
 {
 if (expression == null || expression.Length == 0)
 return null;
 var stack = new Stack<Object>();
 for (int i = 0; i < expression.Length; i++)
 {
 var current = expression[i];
 var isCloseBracket = current == ')';
 if (!isCloseBracket)
 {
 stack.Push(current);
 }
 else
 {
 if (stack.Count < 4)
 return null;
 var operand2 = stack.Pop();
 var operatorChar = stack.Pop();
 var operand1 = stack.Pop();
 var openBracket = (char)stack.Pop();
 if (openBracket != '(' ||
 !checkOperand(operand2) ||
 !checkOperand(operand1) ||
 !checkOperator(operatorChar)
 )
 {
 return null;
 }
 var root = new Node((char)operatorChar);
 root.Left = (operand1.GetType() == typeof(Node)) ? (Node)operand1 : new Node((char)operand1);
 root.Right = (operand2.GetType() == typeof(Node)) ? (Node)operand2 : new Node((char)operand2);
 stack.Push(root);
 }
 }
 if (stack.Count > 1 || stack.Count == 0)
 return null;
 return (Node)stack.Pop();
 }
 /// <summary>
 /// code review July 6, 2018
 /// </summary>
 /// <param name="operand"></param>
 /// <returns></returns>
 private static bool checkOperand(Object operand)
 {
 if (operand.GetType() == typeof(Node))
 return true;
 var number = (char)operand;
 return Operands.IndexOf(number) != -1;
 }
 private static bool checkOperator(Object operatorChar)
 {
 var arithmetic = (char)operatorChar;
 return Operators.IndexOf(arithmetic) != -1;
 }
 }
}

• Pieter Witvoet: This fails to parse inputs like 1, (1), 1+2, ( 1 + 2 ), (1+2+3), (12+34), and so on. What exactly is the purpose of this exercise?
• Jianmin Chen: I did some research about infix expression using parenthesis, but there is no formal definition. I think that as long as I aim to use stack to get linear time to parse the expression. I can design to apply ( and ) to fit my parsing requirement. The extra parenthesis are much cheap in terms of space complexity. If I am the designer to make rules, I like to express 1 + 2 + 3 using this infix expression ((1+2)+3), 1 is not valid infix expression.
• Jianmin Chen: In my opinion, this exercise is very good one to evaluate a candidate how good to be a problem solver in terms of data structure, algorithm, OO design, etc. It is perfect for a code screen.
• Pieter Witvoet: All of those inputs are valid expressions in a wide variety of languages, including C#, so if I were interviewing I would expect an explanation for not being able to parse them. And if the requirements are so vague I would expect the candidate to ask for clarification. Being a good problem solver includes being able to identify the problem, in my opinion.
• Jianmin Chen: code screen is a test on the computer. No human interaction. No compiler, no test case to run against.

Answer 1

OOP

1. Let's start with : private static bool checkOperator(Object operatorChar). You shouldn't use Object if you expect a char. If you want a char , demand a char. Also, checkOperator doesn't really mean anything. Your method is used to check if a character is an operator so, I would rename it isOperator.

   public char Operand { get; set; } // operator sometimes; public Node Left; public Node Right;

2. You sometimes use { get; set}, sometimes not. Use it all. the. time. Fine, it's not always necessary, but it doesn't cost more than not using it and, especially in interview questions regarding OOP, you're better to encapsulate than not.

Comments

public char Operand { get; set; } // operator sometimes;

Okay but, when is it an operator, when is it not? Why is it named operand if it's sometimes an operator. This comment introduces much more confusion that it clarifies things. This is mostly a symptom of a problem with the name of your property.

Your XML comments aren't what they should be. They should be used for documentation, not space/time complexity or history.

Constraints

Your code doesn't support :

1. Numbers higher than 9
2. ((1)+2)

• Jianmin Chen: I think that (1) is a valid infix expression. Extra parenthesis is added to make it easy to parse. I think that the algorithm to construct binary expression tree using infix expression can get complicated, so I may miss a few user cases. By the way, what is list item? Can you explain it using an example?
• IEatBagels: @JianminChen I've never laughed so hard on StackExchange. It's an accident, List Item is what appears by default when you add an item, I'll remove it, there's no point 3 :p And yes my second point is a valid infix expression, but you should test it with your code to see if it works.