You are here:

- Home
- Computing/Technology
- C/C++
- C++
- Priority

Advertisement

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!

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

- Add to this Answer
- Ask a Question

Rating(1-10) | Knowledgeability = 10 | Clarity of Response = 10 | Politeness = 10 |

Comment | Thanks for your replies in a timely manner. |

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**Education/Credentials**

post graduate engineer