Expert: vijayan - 3/2/2009

Question
QUESTION: Hi,

By priority of each expression I mean for instance '*' has a higher priority than "-".

I appreciate your help.


ANSWER: let us say we have a grammar in which integer numbers and the binary operators +, -, * and / are the atoms. let us also assume that
a. * and / have a higher precedence than + and -
b. the operators are left associative. (see: http://en.wikipedia.org/wiki/Operator_associativity)

a common way of evaluating the expression 2 + 3 * 4 - 5 is to first convert it to a Reverse Polish notation or RPN. http://en.wikipedia.org/wiki/Reverse_Polish_notation

one of the well known algorithms used to convert expressions in infix form to RPN is Dijkstra's shunting yard algorithm
http://en.wikipedia.org/wiki/Shunting_yard_algorithm

you have a C++ implementation of the algorithm here:
http://www.devarticles.com/c/a/Cplusplus/Dijkstras-Shunting-Algorithm-with-STL-a

if you are unfamiliar with STL, here is a C implementation:
http://www.friedspace.com/cprogramming/intro2.php  




         


---------- FOLLOW-UP ----------

QUESTION: Thank you so much for the links and your help.
Below you may see my code in Java.

http://rafb.net/p/bixsGQ97.html
I am still stuck about the parts where I compare the actual operand with the one on top as you see in the comments!
Could you please help me on this?


ANSWER: your comments indicate that you are on the right track; to take care of precedence, you need to modify the code.

the algorithm in pseudo-code is very much like your code (with additions  for the commented parts):

// Create operand and operator stacks as empty stacks.

   Begin

   // While input expression still remains, read and process the next token.

   while( not an empty input expression )
       read next token from the input expression


       // Test if token is an operand or operator
       if ( token is an operand )
         // Push operand onto the operand stack.
         OperandStack.Push (token)
       else
         // Token must be an operator.
         if ( token is '(' or OperatorStack.IsEmpty() or PrecedenceOf(token) > PrecedenceOf(OperatorStack.Top()) )
         // Push left parentheses onto the operator stack
         OperatorStack.Push ( token )

         else
         if( token is ')' )
         // Continue to pop operator and operand stacks, building
         // prefix expressions until left parentheses is found.
         // Each prefix expression is push back onto the operand
         // stack as either a left or right operand for the next operator.
         while( OperatorStack.Top() not equal '(' )
         OperatorStack.Pop(operator)
         OperandStack.Pop(RightOperand)
         OperandStack.Pop(LeftOperand)
         operand = operator + LeftOperand + RightOperand
         OperandStack.Push(operand)
         endwhile

         // Pop the left parthenses from the operator stack.
         OperatorStack.Pop(operator)

         else
         if( PrecedenceOf(token) <= PrecedenceOf( top of the operator stack ) )

         // Continue to pop operator and operand stack, building prefix
         // expressions until the stack is empty or until an operator at
         // the top of the operator stack has a lower hierarchy than that
         // of the token.
         while( !OperatorStack.IsEmpty() and . PrecedenceOf(token) lessThen Or Equal to PrecedenceOf(OperatorStack.Top()) )
         OperatorStack.Pop(operator)
         OperandStack.Pop(RightOperand)
         OperandStack.Pop(LeftOperand)
         operand = operator + LeftOperand + RightOperand
         OperandStack.Push(operand)

         endwhile
         // Push the lower precedence operator onto the stack
         OperatorStack.Push(token)

         endif

         endif
         endif
       endif
   endwhile

   // If the stack is not empty, continue to pop operator and operand stacks building
   // prefix expressions until the operator stack is empty.
   while( !OperatorStack.IsEmpty() ) OperatorStack.Pop(operator)
       OperandStack.Pop(RightOperand)
       OperandStack.Pop(LeftOperand)
       operand = operator + LeftOperand + RightOperand

       OperandStack.Push(operand)
   endwhile



   // Save the prefix expression at the top of the operand stack followed by popping
   // the operand stack.

   print OperandStack.Top()

   OperandStack.Pop()



End


---------- FOLLOW-UP ----------

QUESTION: Thanks for your help.
The problem is that I don't know how to come up with the code that checks the priority of the operand.
I already have the algorithm but cannot convert it to the code!!!! :(
if you look at my comments in the code there are a few parts that I left ***** and I put what the algorithm is but can't convert the algorithm to the code itself!

Answer
> The problem is that I don't know how to come up with the code that checks the priority...

that is easy, isn't it? something like this should do:

int priority( char oper )
{
   if( ( oper == '*' ) || ( oper == '/' ) ) return 2 ;
   else if( ( oper == '+' ) || ( oper == '-' ) ) return 1 ;
   else return 0 ;
}

and then:

if( priority(ch) > priority( operators.peek() ) etc.