Expression Evaluation and Syntax Parsing

EXPRESSION EVALUATION AND SYNTAX PARSING

Calculators employing  reverse Polish notation (also known as postfix notation )use a stack structure to hold values.

Expressions can be represented in prefix, postfix or infix notations. Conversion from one form of the expression to another form needs a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most of the programming languages are  context-free languages allowing them to be parsed with stack based machines. Note that natural languages are  context sensitive languages and stacks alone are not enough to interpret their meaning.

Infix, Prefix and Postfix Notation

We are accustomed to write arithmetic expressions with the operation between the two operands: a+b or c/d. If we write a+b*c, however, we have to apply precedence rules to avoid the ambiguous evaluation (add first or multiply first?).

There's no real reason to put the operation between the variables or values. They can just as well precede or follow the operands. You should note the advantage of prefix and postfix: the need for precedence rules and parentheses are eliminated.

Examples of use: ( application of stack )

Arithmetic Expressions: Polish Notation

An arithmetic expression will have operands and operators. Operator precedence listed below:

Highest       :         ($)

Next Highest        :         (*) and (/)

Lowest        :         (+) and (-)

For most common arithmetic operations, the operator symbol is placed in between its two operands. This is called infix notation.

Example:  A + B , E * F

Parentheses can be used to group the operations.

Example: (A + B) * C

Accordingly, the order of the operators and operands in an arithmetic expression does not uniquely determine the order in which the operations are to be performed.

Polish notation refers to the notation in which the operator symbol is placed before its two operands. This is called prefix notation.

Example: +AB, *EF

The fundamental property of polish notation is that the order in which the operations are to be performed is completely determined by the positions of the operators and operands in the expression.

Accordingly, one never needs parentheses when writing expressions in Polish notation.

Reverse Polish Notation refers to the analogous notation in which the operator symbol is placed after its two operands. This is called postfix notation.

Example: AB+, EF*

Here also the parentheses are not needed to determine the order of the operations.

The computer usually evaluates an arithmetic expression written in infix notation in two steps,

1.        It converts the expression to postfix notation.

2.        It evaluates the postfix expression.

In each step, the stack is the main tool that is used to accomplish the given task.

(1)Question :  ( Postfix evaluation )

How to evaluate a mathematical expression using a stack The algorithm for Evaluating a postfix expression ?

•             Initialise   an   empty   stack

•             While   token   remain   in   the   input   stream

–Read next token

–If token is a number, push it into the stack

–Else, if token is an operator, pop top two tokens off the stack, apply the operator, and push the answer back into the stack

•     Pop   the   answer   off   the   stack.

Algorithm postfixexpression

Initialize a stack, opndstk to be empty.

{scan the input string reading one element at a time into symb } While ( not end of input string )

{

Symb := next input character;

If symb is an operand Then

push (opndstk,symb)

Else

[symbol is an operator]

{

Opnd1:=pop(opndstk);

Opnd2:=pop(opndnstk);

Value := result of applying symb to opnd1 & opnd2 Push(opndstk,value);

}

Result := pop (opndstk);

Example:   

6 2 3 + - 3 8 2 / + * 2     $ 3 +

The Final value in the STACK is 52. This is the answer for the given expression.

(2) run time stack for function calls ( write factorial number calculation procedure) push local data and return address onto stack

return by popping off local data and then popping off address and returning to it return value can be pushed onto stack before returning, popped off by caller

(3) expression parsing

e.g. matching brackets: [ ... ( ... ( ... ) [ ...( ... ) ...] ... ) ... ] push left ones, pop off and compare with right ones

4) INFIX TO POSTFIX CONVERSION

Infix expressions are often translated into postfix form in which the operators appear after their operands.

Steps:

1. Initialize an empty stack.

2.   Scan the Infix Expression from left to right.

3. If the scannned character is an operand, add it to the Postfix Expression.

4. If the scanned character is an operator and if the stack is empty, then push the character to stack.

5.   If the scanned character  is an operator and the stack is not empty, Then

(a)  Compare the precedence of the character with the operator on the top of the stack.

(b) While operator at top of stack has higher precedence over the scanned character & stack is not empty.

(i)   POP the stack.

(ii)   Add the Popped character to Postfix String.

( c )  Push the scanned character to stack.

6.  Repeat the steps 3-5 till all the characters

7.   While stack is not empty,

(a)  Add operator in top of stack

(b)   Pop the stack.

8.     Return the Postfix string.

Algorithm Infix to Postfix conversion ( without parenthesis)

1.     Opstk = the empty stack;

2.     while ( not end of input )

{

symb = next input character;

3.       if ( symb is an operand )

add symb to the Postfix String

4.   else

{

5.         While( ! empty (opstk) && prec ( stacktop ( opstk), symb) )

{

topsymb = pop ( opstk )

add topsymb to the Postfix String; } / * end of while */

Push(opstk, symb);

} /* end  else */

6.                       } /*  end while * /

7.     While( ! empty ( opstk ) )

{

topsymb = pop (opstk)

add topsymb to the Postfix String

}  /* end of while */

8.     Return the Postfix String.

OTHER APPLICATIONS OF STACK

Some of the applications of stack are :

(i)  Evaluating arithmetic expression

(ii) Balancing the symbols

(iii) Towers of Hannoi

(iv) Function Calls.

(v)8 Queen Problem.