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

you have a C++ implementation of the algorithm here:

if you are unfamiliar with STL, here is a C implementation:


[an error occurred while processing this directive]---------- FOLLOW-UP ----------

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

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.


   // 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)
         // 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 )

         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 '(' )
         operand = operator + LeftOperand + RightOperand

         // Pop the left parthenses from the operator stack.

         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()) )
         operand = operator + LeftOperand + RightOperand

         // Push the lower precedence operator onto the stack



   // 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)
       operand = operator + LeftOperand + RightOperand


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

   print OperandStack.Top()



---------- 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!

> 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.  


All Answers

Answers by Expert:

Ask Experts




my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.


about 15 years or so

post graduate engineer

©2017 About.com. All rights reserved.

[an error occurred while processing this directive]