# C++/Priority

Question
QUESTION: Hi,

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

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

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

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!

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

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.
Questioner's Rating
 Rating(1-10) Knowledgeability = 10 Clarity of Response = 10 Politeness = 10 Comment Thanks for your replies in a timely manner.

C++

Volunteer

#### vijayan

##### Expertise

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.