Evaluate Postfix expression for interviews

C# .NET language

In this new post, I will show how to evaluate Postfix expression for your interviews as a C# developer. When you have interviews, you never know what they will ask you. Sometimes, the easiest question could be the most complicated thing. I don’t know you, but I found this snap test interview quite boring. For example, when in the real work you have to evaluate a Postfix expression?

The source code of this test is on GitHub.

Reverse Polish notation (RPN) or Postfix notation

Reverse Polish notation (RPN), also known as reverse Łukasiewicz notation, Polish postfix notation or simply postfix notation, is a mathematical notation in which operators follow their operands, in contrast to Polish notation (PN), in which operators precede their operands. It does not need any parentheses as long as each operator has a fixed number of operands. The description “Polish” refers to the nationality of logician Jan Łukasiewicz, who invented Polish notation in 1924.

In reverse Polish notation, the operators follow their operands; for instance, to add 3 and 4 together, one would write 3 4 + rather than 3 + 4. If there are multiple operations, operators are given immediately after their final operands (often an operator takes two operands, in which case the operator is written after the second operand); so, the expression written 3 − 4 + 5 in conventional notation would be written 3 4 − 5 + in reverse Polish notation: 4 is first subtracted from 3, then 5 is added to it.

An advantage of reverse Polish notation is that it removes the need for parentheses that are required by infix notation. While 3 − 4 × 5 can also be written 3 − (4 × 5), that means something quite different from (3 − 4) × 5. In reverse Polish notation, the former could be written 3 4 5 × −, which unambiguously means 3 (4 5 ×) − which reduces to 3 20 − (which can further be reduced to -17); the latter could be written 3 4 − 5 × (or 5 3 4 − ×, if keeping similar formatting), which unambiguously means (3 4 −) 5 ×.

The initial code

After 2 hours of discussion about interesting topics, they showed me the following code:

using System;
using System.Collections.Generic;

namespace ReversePostfix
{
    public class Test
    {  
        public static void Main()
        {
            RunTestCase(10, new[] { "5", "2", "*" }); // 5 * 2 = 10
            RunTestCase(13, new[] { "10", "2", "*", "6", "+", "2", "/" }); // ((10 * 2) + 6) / 2 = 13
            RunTestCase(95, new[] { "100", "10", "-", "30", "6", "/", "+" }); // (100 - 10) + (30 / 6) = 95
            RunTestCase(6, new[] { "10", "7", "-", "!" }); // (10 - 7)! = 6 
        }  
        
        public static double Calculate(IEnumerable<string> input) {

        }

       // ---------------------------------------------------------------------------
        public static double CalculateFactorial(double input)
        {
            if (input > 100)
            {
                throw new InvalidOperationException("This will take too long for the interview.");
            }

            var num  = input;
            for (var i = 1; i < input; ++i)
            {
                num *= input - i;
            }

            return num;
        }

        public static void RunTestCase(double expectedResult, IEnumerable<string> input)
        {
            var result = Calculate(input);
            if (Math.Abs(result - expectedResult) < 0.001)
            {
                Console.WriteLine("Pass");
            }
            else
            {
                Console.WriteLine("Fail: Expected = {0}, Actual = {1}. Input = '{2}'", 
                                  expectedResult, result, string.Join(",", input));
            }
        }
    }
}

So, what is this code doing? Obviously, Main is calling the function RunTestCase that checks if the function Calculate returns the expected value. The function CalculateFactorial is totally useless.

Now, if you don’t know the Postfix notation, you can’t solve the problem in the academic way. So, the first question passes in my mind is: do I really want to work with them?

Using Stack

A Stack represents a last-in, first-out collection of objects. It is used when you need last-in, first-out access to items. It is both a generic and non-generic type of collection. The generic stack is defined in System.Collections.Generic namespace whereas non-generic stack is defined under System.Collections namespace, here we will discuss non-generic type stack. A stack is used to create a dynamic collection that grows, according to the need of your program. In a stack, you can store elements of the same type or different types.

Stack representation - Evaluate Postfix expression for interviews
Stack representation

The below diagram illustrates the Stack class hierarchy:

Stack class hierarchy - Evaluate Postfix expression for interviews
Stack class hierarchy

Functions of Stack in C#

Whenever we need access to the elements of the stack in last in and first out order, we the collection of objects called Stack. The process of adding an element to the Stack is called pushing the elements to the stack and the process of removing an element from the stack is called popping an element from the Stack.

Stack is a dynamic collection of elements because the size of the stack increases with the addition of elements to the stack. The number of elements that a stack can hold is called the capacity of the stack. As the size of the stack increases with the addition of elements to the stack, the capacity of the stack also increases through reallocation.

There can be duplicate elements allowed in the stack. Null is accepted by the stack as a valid value for type, references.

There are several constructors in Stack in C#. They are:

  • Stack(): A new instance of the stack class is initialized which is empty whose initial capacity is the default.
  • Stack(ICollection): A new instance of the stack class is initialized which consists of elements that are taken from a collection specified as a parameter and the initial capacity is the same as the number of elements taken from the collection specified as a parameter.
  • Stack(Int32): A new instance of the stack class is initialized which is empty whose initial capacity is either the initial capacity specified as the parameter or the initial capacity which is default.

Methods in C# Stack

There are several methods in Stack in C#. They are:

  • Clear(): The objects of the stack are removed using the Clear() method.
  • Push(Object): An object specified as the parameter is inserted at the top of the stack using the Push(Object) method.
  • Contains(Object): The Contains(Object) method is used to determine if an element is present in the stack.
  • Peek(): The object specified at the top of the stack is returned but is not removed using the Peek() method.
  • Pop(): The object specified at the top of the stack is returned and is removed using the Pop() method.

How to create a Stack

So, this is a simple definition of a Stack and remember to add the using System.Collections

using System.Collections;
Stack stack_name = new Stack();

How to use Stack

Now, see the following code:

// C# program to illustrate how to
// create a stack
using System;
using System.Collections;
 
class StackExample {
 
    // Main Method
    static public void Main()
    {
 
        // Create a stack
        // Using Stack class
        Stack my_stack = new Stack();
 
        // Adding elements in the Stack
        // Using Push method
        my_stack.Push("PureSourceCode");
        my_stack.Push("psc");
        my_stack.Push('ER');
        my_stack.Push(null);
        my_stack.Push(1234);
        my_stack.Push(490.98);
 
        // Accessing the elements
        // of my_stack Stack
        // Using foreach loop
        foreach(var elem in my_stack)
        {
            Console.WriteLine(elem);
        }
    }
}

The output is:

490.98
1234

ER
psc
PureSourceCode

How to remove a Stack

So, in Stack, you are allowed to remove elements from the stack. The Stack class provides two different methods to remove elements and the methods are:

  • Clear: This method is used to remove all the objects from the stack.
  • Pop: This method removes the beginning element of the stack.
// C# program to illustrate how to
// remove elements from the stack
using System;
using System.Collections;
 
class StackExample {
 
    // Main Method
    static public void Main()
    {
 
        // Create a stack
        // Using Stack class
        Stack my_stack = new Stack();
 
        // Adding elements in the Stack
        // Using Push method
        my_stack.Push("PureSourceCode");
        my_stack.Push("psc");
        my_stack.Push("123");
        my_stack.Push("puresourcecode");
 
        Console.WriteLine("Total elements present in"+
                    " my_stack: {0}", my_stack.Count);
                                                     
        my_stack.Pop();
 
        // After Pop method
        Console.WriteLine("Total elements present in "+
                      "my_stack: {0}", my_stack.Count);
 
                                                    
        // Remove all the elements
        // from the stack
        my_stack.Clear();
 
        // After Pop method
        Console.WriteLine("Total elements present in "+
                      "my_stack: {0}", my_stack.Count);
                                                    
    }
}

The output is:

Total elements present in my_stack: 4
Total elements present in my_stack: 3
Total elements present in my_stack: 0

How to get the topmost element of the Stack?

In Stack, you can easily find the topmost element of the stack by using the following methods provided by the Stack class:

  • Pop: This method returns the object at the beginning of the stack with modification means this method removes the topmost element of the stack.
  • Peek: This method returns the object at the beginning of the stack without removing it.
// C# program to illustrate how to
// get topmost elements of the stack
using System;
using System.Collections;
 
class StackExample {
 
    // Main Method
    static public void Main()
    {
 
        // Create a stack
        // Using Stack class
        Stack my_stack = new Stack();
 
        // Adding elements in the Stack
        // Using Push method
        my_stack.Push("PureSourceCode");
        my_stack.Push("psc");
        my_stack.Push("123");
        my_stack.Push("puresourcecode");
 
        Console.WriteLine("Total elements present in"+
                     " my_stack: {0}",my_stack.Count);
                                                    
        // Obtain the topmost element
        // of my_stack Using Pop method
        Console.WriteLine("Topmost element of my_stack"
                          + " is: {0}",my_stack.Pop());
                           
        Console.WriteLine("Total elements present in"+
                    " my_stack: {0}", my_stack.Count);
                          
        // Obtain the topmost element
        // of my_stack Using Peek method
        Console.WriteLine("Topmost element of my_stack "+
                              "is: {0}",my_stack.Peek());
                           
 
        Console.WriteLine("Total elements present "+
                 "in my_stack: {0}",my_stack.Count);
                           
    }
}

The output is:

Total elements present in my_stack: 4
Topmost element of my_stack is: puresourcecode
Total elements present in my_stack: 3
Topmost element of my_stack is: 123
Total elements present in my_stack: 3

How to check the availability of elements in the stack?

In a stack, you can check whether the given element is present or not using Contains() method. Or in other words, if you want to search an element in the given stack use Contains() method. This method returns true if the element present in the stack. Otherwise, return false.

Note: The Contains() method takes O(n) time to check if the element exists in the stack. This should be taken into consideration while using this method.

using System;
using System.Collections;

class StackExample {

	// Main Method
	static public void Main()
	{

		// Create a stack
		// Using Stack class
		Stack my_stack = new Stack();

		// Adding elements in the Stack
		// Using Push method
        my_stack.Push("PureSourceCode");
        my_stack.Push("psc");
        my_stack.Push("123");
        my_stack.Push("puresourcecode");

		// Checking if the element is
		// present in the Stack or not
		if (my_stack.Contains("PureSourceCode") == true)
		{
			Console.WriteLine("Element is found...!!");
		}

		else
		{
			Console.WriteLine("Element is not found...!!");
		}
	}
}

The output is:

Element is found...!!

Generic Stack Vs Non-Generic Stack

Generic StackNon-Generic Stack
Generic stack is defined under System.Collections.Generic namespace.Non-Generic stack is defined under System.Collections namespace.
Generic stack can only store same type of elements.Non-Generic stack can store same type or different types of elements.
There is a need to define the type of the elements in the stack.There is no need to define the type of the elements in the stack.
It is type-safe.It is not type-safe.

Postfix

Evaluate Postfix expression

So, now we have some context and clarity about the Stack, we can start to evaluate Postfix expression for our interviews. First, have a look at the test cases

RunTestCase(10, new[] { "5", "2", "*" }); // 5 * 2 = 10
RunTestCase(13, new[] { "10", "2", "*", "6", "+", "2", "/" }); // ((10 * 2) + 6) / 2 = 13
RunTestCase(95, new[] { "100", "10", "-", "30", "6", "/", "+" }); // (100 - 10) + (30 / 6) = 95
RunTestCase(6, new[] { "10", "7", "-", "!" }); // (10 - 7)! = 6 

Look at the first line. I read from the array the first element and I save it in a variable. Then, I read the second element. I have to check if it is an operator and, if it is not, save it in another variable. Then, I read the last value, check if it is an operator and then perform the calculation.

Then, you have the last test. In this case, there is an ! operator. If you see the result of the test, the value is 6. So, I think in this case the exclamation point multiplies the value with 2.

Now, I have to repeat the process for each element of the array. Don’t be scared about the parenthesis! This is a simple test how to evaluate Postfix expression for interviews. Do you think the interviewers what to spend a lot of time with you? Don’t do like me: think the simplest solution you can. For example, I was thinking how to use Linq or other complicated structure. Keep it simple. They are not too smart 😀

This test is an academic code designed to see if you know the basic commands. So, the best code I can write for that is the following:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ReversePostfix
{
	public class Test
	{
		public static void Main()
		{
			RunTestCase(10, new[] { "5", "2", "*" }); // 5 * 2 = 10
			RunTestCase(13, new[] { "10", "2", "*", "6", "+", "2", "/" }); // ((10 * 2) + 6) / 2 = 13
			RunTestCase(95, new[] { "100", "10", "-", "30", "6", "/", "+" }); // (100 - 10) + (30 / 6) = 95
			RunTestCase(6, new[] { "10", "7", "-", "!" }); // (10 - 7)! = 6 
		}

		public static double Calculate(IEnumerable<string> input)
		{
			Stack<double> stack = new Stack<double>();

			foreach (string element in input)
			{
				if (!"+-*/!".Contains(element))
				{
					stack.Push(Convert.ToDouble(element));
					continue;
				}

				double second = stack.Count() > 0 ? stack.Pop() : 0;
				double first = stack.Count() > 0 ? stack.Pop() : 0;
				double ans = 0;
				switch (element)
				{
					case "+":
						ans = first + second;
						break;
					case "-":
						ans = first - second;
						break;
					case "/":
						ans = first / second;
						break;
					case "*":
						ans = first * second;
						break;
					case "!":
						ans = second * 2;
						break;

				}
				stack.Push(ans);
			}
			return stack.Pop();
		}

		public static void RunTestCase(double expectedResult, IEnumerable<string> input)
		{
			var result = Calculate(input);
			if (Math.Abs(result - expectedResult) < 0.001)
			{
				Console.WriteLine("Pass");
			}
			else
			{
				Console.WriteLine("Fail: Expected = {0}, Actual = {1}. Input = '{2}'", 
							      expectedResult, result, string.Join(",", input));
			}
		}
	}
}

Wrap up

In conclusion, this is an implementation of how evaluate Postfix expression for interviews. I hope this code can help you. Please use the comment below or the forum to give me your feedback or suggest more tests.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.