Conversion of Infix expressions to Postfix expressions

We generally write expressions using infix notation, meaning 3 + 4, but machines do not typically processes expressions in this format.  Machines typically require the expressions to be translated into Postfix notation, meaning 3 4 +.  Your compiler needs to be able to convert the infix notation expressions from the Smada language into postfix notation expressions that can then be evaluated.

Given the characteristics of postfix notation, it is common for compilers to use stacks to assist the process of evaluating expressions and generating machine language code.

The algorithm below can be used to convert an infix expression to a postfix expression.  This algorithm requires a single left-to-right pass of the expression. It also requires a stack object to support the operation.  This stack must be an instance of the stack from the Standard Template Library.

You need to provide the capability to convert multiple digit integer operands and single character variable name operands. You may assume that a valid infix expression is entered. 

The functionality for this section of the compiler needs to take an infix expression and convert it to the postfix expression.  For example:

(62 + 25) * 5 - 83 / 4      // Infix notation

becomes

62 25 + 5 * 83 4 / -    //Postfix notation

The compiler needs to read the expression into character array infix, and use the stack class to help create the postfix expression in character array postfix. The algorithm for creating a postfix expression is as follows:

1)       Push a left parenthesis '(' onto the stack.

2)       While the stack is not empty, read infix expression from left to right and do the following:

·         If the current character in infix is a digit, copy it to the next element of postfix.

·         If the current character in infix is a left parenthesis, push it onto the stack.

·         If the current character in infix is an operator,

Pop operators (if there are any) at the top of the stack while they have equal or higher precedence than the current operator, and insert the popped operators in postfix.

Push the current character in infix onto the stack.

·         If the current character in infix is a right parenthesis

Pop operators from the top of the stack and insert them in postfix until a left parenthesis is at the top of the stack.

Pop (and discard) the left parenthesis from the stack.

The following arithmetic operations are allowed in an expression:

+ addition
- subtraction
* multiplication
/ division  

You need to provide the capability to:

1. Convert the infix expression to postfix notation.

2. Determine if a character is an operator or not.

3. Determine if the precedence of an operator is less than, equal to or greater than the precedence of another operator. The function to implement this capability should return -1, 0 and 1, respectively.

4. You also need to be able to print the contents of the stack.

Evaluating Postfix Expressions

Now that you have an algorithm to convert the infix notation to postfix notation, it is time to evaluating the postfix expression you created.

A basic algorithm to evaluate a postfix expression is as follows:

    1) Append the null character ('\0') to the end of the postfix expression. When the null character is encountered, no further processing is necessary.

    2) While '\0' has not been encountered, read the expression from left to right.

If the current character is a digit,

Push its integer value onto the stack (the integer value of a digit character is its value in the computer’s character set minus the value of '0' in the computer’s character set).

Otherwise, if the current character is an operator,

Pop the two top elements of the stack into variables x and y.

Calculate y operator x.

Push the result of the calculation onto the stack.

    3)       When the null character is encountered in the expression, pop the top value of the stack. This is the result of the postfix expression.

Note: In step 2) above, if the operator is '/', the top of the stack is 2 and the next element in the stack is 8, then pop 2 into x, pop 8 into y, evaluate 8 / 2 and push the result, 4, back onto the stack. This note also applies to operator '-'. The arithmetic operations allowed in an expression are:

+ addition
- subtraction
* multiplication
/ division  

The algorithm above actually evaluates the postfix expression.  You need to modify the algorithm to implement a “hook” so that SML instructions are produced.  The algorithm above needs to be modified to search the symbol table for each symbol it encounters (and possibly insert it), determine the symbol’s corresponding memory location, and push the memory location onto the stack (instead of the symbol).  When an operator is encountered in the postfix expression, the two memory locations at the top of the stack are popped and the machine language representing the operation is produced using the memory locations as operands.  The result of each subexpression is stored in a temporary memory location in and pushed back on the stack so the evaluation of the postfix expression can continue.  When the postfix evaluation is complete, the memory location is popped and SML instructions are generated to assign the result to the variable at the left of the let statement.