# Postfix Notation: An Interview Exercise

02 Aug 2019 #tutorial #interview #csharpYou are applying for your first position or for a new job. You are asked to complete a coding exercise: evaluate an expression in postfix notation. Let’s see what is postfix notation and how to evaluate postfix expressions in C#.

## What is Postfix Notation?

Math and some programming languages use the infix notation. It places the operator between the two operands. And, it uses parenthesis to group operations. For example, `a + b`

and `(a + b)*c`

.

**Unlinke infix notation, postfix notation places the operator after the two operands. And, it doesn’t use any parenthesis to group expresions. For example, a b + , and a b + c * are two expression in postfix notation.**

Postfix expressions are evaluated from left to right. The expression `2 3 1 * + 9 -`

in postfix notation is equivalent to `(2 + (3 * 1)) - 9`

.

## Interview Question

This is your interview question: Write a C# program to evaluate a postfix mathematical expression. For example, `1 1 +`

, `1 1 1 + +`

, `1 1 + 2 3 * -`

.

During your technical interview, don’t rush to start coding right away. Follow the next steps:

- Understand the problem
- Come up with some examples.
*What’s the simplest case? Any edge cases?* - Ask clarification questions.
*Do you need to validate your input values?* - Think out loud your solution. Your interviewer wants to see your thought process.
- Make assumptions on the input. Start with the simplest case and work through a complete solution.

## Evaluate postfix expressions

To evaluate a postfix expression, you need a stack.

**A stack is a pile-like data structure**. Stacks support two operations: add something to the pile, **push**, and remove something from the pile, **pop**.

When evaluating a postfix notation, we use a stack to hold either values from the input or already computed values.

This is the pseudocode to evaluate a postfix expression:

- Create an stack
- Split input string
- If the first splitted value is a number, push it to the stack.
- But, if it’s an operator, pop the two operands from the stack. Do the Math operation and push the result back to the stack.
- Go to next splitted value and repeat
- Finally, return value in the stack

### Let’s C#!!!

Now, head to Visual Studio or Visual Studio Code and create a new project. This is how we evaluate a postfix expression in C#.

First, let’s split the input string with the `Split()`

method. To identify the operators and operands, we can use either string comparisons or regular expressions. Let’s use regular expressions.

```
Regex _operandRegex = new Regex(@"-?[0-9]+");
Regex _operatorRegex = new Regex(@"[+\-*\/]");
public string Evaluate(string postfixExpression)
{
var tokens = new Stack();
string[] rawTokens = postfixExpression.Split(' ');
foreach (var t in rawTokens)
{
if (_operandRegex.IsMatch(t))
{
tokens.Push(t);
}
else if (_operatorRegex.IsMatch(t))
{
var t1 = tokens.Pop().ToString();
var t2 = tokens.Pop().ToString();
var op = t;
var result = EvaluateSingleExpression(t2, t1, op);
if (result != null)
{
tokens.Push(result);
}
}
}
if (tokens.Count > 0)
{
return tokens.Pop().ToString();
}
return "";
}
private static string EvaluateSingleExpression(string value1, string value2, string op)
{
var operand1 = Convert.ToDouble(value1);
var operand2 = Convert.ToDouble(value2);
if (op == "+")
{
var result = operand1 + operand2;
return Convert.ToString(result);
}
// Similar logic for other operators
return null;
}
```

Voila! That’s how we can evaluate postfix expressions in C#. For more tips to prepare yourself for your next interview, check my interview tips. Also, check my post on the difference between Func and Action in C# and how to solve the two-sum problem. Those are another two common interview questions.

*Happy coding!*