Coding challenge | Microsoft interview | Part 2

A stack machine is a simple system that performs arithmetic operations on an input string of numbers and operators. Initially the stack is empty. The machine processes a string of characters in the following way:

• the characters of the string are processed one by one;
• if the current character is a digit [0–9], the machine pushes the value of that digit onto its stack;
• if the current character is +, the machine pops the two topmost values from its stack, adds them and pushes the result onto the stack;
• if the current character is *, the machine pops the two topmost values from its stack, multiplies them and pushes the result onto the stack;
• after the machine has processed the whole string it returns the topmost value of its stack as the result;
• the machine reports an error if any operation it performs (addition or multiplication) results in an overflow;
• the machine reports an error if it tries to pop an element from its stack when the stack is empty, or if the stack is empty after the machine has processed the whole string.

For example, given the string “13+627+” the machine will perform the following operations:

character 	| comment                | stack
 -----------------------------------------------
            |                        | 
 '1'        | push 1 onto the stack  | 1
            |                        | 
 '3'        | push 3 onto the stack  | 1, 3
            |                        | 
 '+'        | perform addition       | 4
            |                        | 
 '6'        | push 6 onto the stack  | 4, 6
            |                        | 
 '2'        | push 2 onto the stack  | 4, 6, 2
            |                        | 
 '*'        | perform multiplication | 4, 12
            |                        | 
 '7'        | push 7 onto the stack  | 4, 12, 7
            |                        | 
 '+'        | perform addition       | 4, 19
            |                        | 
 '*'        | perform multiplication | 76
            |                        |

The machine will return 76 as the result as it is the topmost element of its stack.

Write a function that, given a string S consisting of N characters containing input for the stack machine, returns the result the machine would return if given this string. The function should return -1 if the machine would report an error when processing the string.

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

Solution

using System;
using System.Linq;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
class Solution 
{
    
    public static int AssignmentWithStack(string instructions)
    {
        try { 
            Stack<int> stack = new Stack<int>();
            char[] instructionsArray = instructions.ToCharArray();
            for (int i = 0; i < instructionsArray.Length; i++)
            {
                switch (instructionsArray[i])
                {
                    case '+':
                        stack.Push(stack.Pop() + stack.Pop());
                        break;
                    case '*':
                        stack.Push(stack.Pop() * stack.Pop());
                        break;
                    default:
                        int itemToAdd = Convert.ToInt32(instructionsArray[i].ToString());
                        stack.Push(itemToAdd);
                        break;
                }
            }
            return stack.Last();
        } 
        catch
        {
            return -1;
        }
    }
    public static int AssignmentWithArray(string instructions)
    {
        try
        {
            int index = 0;
            int[] stack = new int[instructions.Length - Regex.Matches(instructions, @"[^\d]").Count];
            
            char[] instructionsArray = instructions.ToCharArray();
            for (int i = 0; i < instructionsArray.Length; i++)
            {
                switch (instructionsArray[i])
                {
                    case '+':
                        stack[index - 2] = stack[index - 1] + stack[index - 2];
                        index--;
                        break;
                    case '*':
                        stack[index - 2] = stack[index - 1] * stack[index - 2];
                        index--;
                        break;
                    default:
                        stack[index] = Convert.ToInt32(instructionsArray[i].ToString());
                        index++;
                        break;
                }
            }
            return stack[index-1];
        }
        catch
        {
            return -1;
        }
    }
}

Performance

Stopwatch stopWatch = new Stopwatch();

stopWatch.Start();
var result = AssignmentWithStack("13+62*7+*");
stopWatch.Stop();
Console.WriteLine($"Result:{result}");
Console.WriteLine("Ticks: " + stopWatch.Elapsed.Ticks);
stopWatch.Reset();
stopWatch.Start();
result = AssignmentWithArray("13+62*7+*");
stopWatch.Stop();
Console.WriteLine($"Result:{result}");
Console.WriteLine("Ticks: " + stopWatch.Elapsed.Ticks);

The output is:

Result:76
Ticks: 137579
Result:76
Ticks: 13283

As you can see, in this case, working with a System.Array is faster than with a Collections.Stack object.