Implementation

I wrote the script in Python3.

Stack Class

My script has a stack class with the normal methods of pop, peek, push and print, str, len methods.

Functions for Converting expressions

I also wrote 5 functions to support converting expressions between infix, prefix, and postfix forms. There are 3 main recursive functions prefix→infix, infix→postfix, postfix→infix. The other 2 functions postfix→prefix and prefix→postfix call the main functions as intermediary functions.

Time Complexity

All the functions run in O(n) as they must go through every element in the input expression. Each element is processed once: it is either popped or pushed. The functions that call the basic main functions (postfix→prefix and prefix→postfix) will run in T(2n) since they are processed twice; they are also T(2n) → O(n).

Use of stacks

I used stacks as a build the output expression and to hold the operators and delimiters. Stacks especially make sense to hold delimiters; delimiters come in pairs and separate the expression into different depths as you work your way in then out of the expression. As you read your way into the expression, you collect the open delimiters. If you encounter any closed delimiters, its match will be the last delimiter you’ve encountered (the element on the top of the stack). You do not have to access elements near the bottom of the stack.

Other supporting functions

I wrote a support function to check if the symbol was an operand or operator. I also wrote a function to check if the delimiters were balanced.

Error handling and Test Cases

The function InfixToPostfix() reads in infix expressions which may include delimiters. The function checks if the delimiters are balanced. It will also replace curvy or square brackets as parenthesis.

I tested if the script could handle other delimiters with the infix expression: ((A+(([B^C]D)-{(E+F)/(GH)}))+I)

I tested if the exception caught unbalanced delimiters with this infix expression:

A+((B-C)*(D-E)+F)/G)^(H-J)