Scribd
Upload
8 views17 pages

Stack Problems 1

The document outlines the processes for converting infix expressions to postfix and prefix expressions, detailing the logic and steps involved in each conversion. It includes specific rules for handling operators, operands, and parentheses during the conversion. Additionally, it mentions the evaluation of postfix and prefix expressions, although the details for evaluation are not provided.

Uploaded by

terone3505
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views17 pages

Stack Problems 1

The document outlines the processes for converting infix expressions to postfix and prefix expressions, detailing the logic and steps involved in each conversion. It includes specific rules for handling operators, operands, and parentheses during the conversion. Additionally, it mentions the evaluation of postfix and prefix expressions, although the details for evaluation are not provided.

Uploaded by

terone3505
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Stack Problems - I

Infix, Postfix and Prefix Expressions


Infix to Postfix Conversion (Logic)
Infix to Postfix Conversion
1. If we have an opening parenthesis "(", we push it into the stack.

2. If we have an operand, we append it to our postfix expression.

3. If we have a closing parenthesis ")" we keep popping out elements from the top of the stack and append them to our postfix
expression until we encounter an opening parenthesis. We pop out the left parenthesis without appending it.

4. If we encounter an operator:-

4.1. If the operator has higher precedence than the one on top of the stack (We can compare ), we push it in the stack.

4.2. If the operator has lower or equal precedence than the one on top of the stack, we keep popping out and appending it to the
postfix expression.

5. When the last token of infix expression has been scanned, we pop the remaining elements from stack and append them to our
postfix expression.*
Evaluation of Postfix Expression (Logic)
Infix to Prefix Conversion (Logic)
Infix to Prefix Conversion
1. First, reverse the infix expression given in the problem.
2. Scan the expression from left to right.
3. Whenever the operands arrive, print them.
4. If the operator arrives and the stack is found to be empty, then simply push the operator into the stack.
5. If the incoming operator has higher precedence than the TOP of the stack, push the incoming operator into the stack.
6. If the incoming operator has the same precedence with a TOP of the stack, push the incoming operator into the stack.
7. If the incoming operator has lower precedence than the TOP of the stack, pop, and print the top of the stack. Test the incoming
operator against the top of the stack again and pop the operator from the stack till it finds the operator of a lower precedence or
same precedence.
8. If the incoming operator has the same precedence with the top of the stack and the incoming operator is ^, then pop the top of
the stack till the condition is true. If the condition is not true, push the ^ operator.
9. When we reach the end of the expression, pop, and print all the operators from the top of the stack.
10. If the operator is ')', then push it into the stack.
11. If the operator is '(', then pop all the operators from the stack till it finds ) opening bracket in the stack.
12. If the top of the stack is ')', push the operator on the stack.
13. At the end, reverse the output.
Evaluation of Prefix Expression (Logic)
Convert a Postfix expression to a Prefix Expression

You might also like