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;
        }
    }
}

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)