conversion from infix to prefix

Question

I am preparing for an exam where i couldn't understand the convertion of infix notation to polish notation for the below expression:

(a–b)/c*(d + e – f / g)

Can any one tell step by step how the given expression will be converted to prefix?

Answer 1

Maybe you're talking about the Reverse Polish Notation? If yes you can find on wikipedia a very detailed step-to-step example for the conversion; if not I have no idea what you're asking :(

You might also want to read my answer to another question where I provided such an implementation: C++ simple operations (+,-,/,*) evaluation class

Answer 2

(a–b)/c*(d + e – f / g)

remember scanning the expression from leftmost to right most start on parenthesized terms follow the WHICH COMES FIRST rule... *, /, % are on the same level and higher than + and -.... so (a-b) = -bc prefix (a-b) = bc- for postfix another parenthesized term: (d + e - f / g) = do move the / first then plus '+' comes first before minus sigh '-' (remember they are on the same level..) (d + e - f / g) move / first (d + e - (/fg)) = prefix (d + e - (fg/)) = postfix followed by + then - ((+de) - (/fg)) = prefix ((de+) - (fg/)) = postfix

(-(+de)(/fg)) = prefix so the new expression is now -+de/fg (1) ((de+)(fg/)-) = postfix so the new expression is now de+fg/- (2)

(a–b)/c* hence

1. (a-b)/c*(d + e – f / g) = -bc prefix [-ab]/c*[-+de/fg] ---> taken from (1) / c * do not move yet so '/' comes first before '*' because they on the same level, move '/' to the rightmost : /[-ab]c * [-+de/fg] then move '*' to the rightmost

   • / [-ab]c[-+de/fg] = remove the grouping symbols = */-abc-+de/fg --> Prefix

2. (a-b)/c*(d + e – f / g) = bc- for postfix [ab-]/c*[de+fg/-]---> taken from (2) so '/' comes first before '' because they on the same level, move '/' to the leftmost: [ab-]c[de+fg/-]/ then move '' to the leftmost [ab-] c [de+fg/-]/ = remove the grouping symbols= a b - c d e + f g / - / * --> Postfix

Answer 3

(a–b)/c*(d + e – f / g)

step 1: (a-b)/c*(d+e- /fg))

step 2: (a-b)/c*(+de - /fg)

step 3: (a-b)/c * -+de/fg

Step 4: -ab/c * -+de/fg

step 5: /-abc * -+de/fg

step 6: */-abc-+de/fg

This is prefix notation.

Answer 4

here is an java implementation for convert infix to prefix and evaluate prefix expression (based on rajdip's algorithm)

import java.util.*;

public class Expression {
    private static int isp(char token){
        switch (token){
            case '*':
            case '/':
                return 2;
            case '+':
            case '-':
                return 1;
            default:
                return -1;
        }
    }
    private static double calculate(double oprnd1,double oprnd2,char oprt){
        switch (oprt){
            case '+':
                return oprnd1+oprnd2;
            case '*':
                return oprnd1*oprnd2;
            case '/':
                return oprnd1/oprnd2;
            case '-':
                return oprnd1-oprnd2;
            default:
                return 0;
        }
    }
    public static String infix2prefix(String infix) {
        Stack<String> OperandStack = new Stack<>();
        Stack<Character> OperatorStack = new Stack<>();
        for(char token:infix.toCharArray()){
            if ('a' <= token && token <= 'z')
                OperandStack.push(String.valueOf(token));
            else if (token == '(' || OperatorStack.isEmpty() || isp(token) > isp(OperatorStack.peek()))
                OperatorStack.push(token);
            else if(token == ')'){
                while (OperatorStack.peek() != '(') {
                    Character operator = OperatorStack.pop();
                    String RightOperand = OperandStack.pop();
                    String LeftOperand = OperandStack.pop();
                    String operand = operator + LeftOperand + RightOperand;
                    OperandStack.push(operand);
                }
                OperatorStack.pop();
            }
            else if(isp(token) <= isp(OperatorStack.peek())){
                while (!OperatorStack.isEmpty() && isp(token)<= isp(OperatorStack.peek())) {
                    Character operator = OperatorStack.pop();
                    String RightOperand = OperandStack.pop();
                    String LeftOperand = OperandStack.pop();
                    String operand = operator + LeftOperand + RightOperand;
                    OperandStack.push(operand);
                }
                OperatorStack.push(token);
            }
        }
        while (!OperatorStack.isEmpty()){
            Character operator = OperatorStack.pop();
            String RightOperand = OperandStack.pop();
            String LeftOperand = OperandStack.pop();
            String operand = operator + LeftOperand + RightOperand;
            OperandStack.push(operand);
        }
        return OperandStack.pop();
    }
    public static double evaluatePrefix(String prefix, Map values){
        Stack<Double> stack = new Stack<>();
        prefix = new StringBuffer(prefix).reverse().toString();
        for (char token:prefix.toCharArray()){
            if ('a'<=token && token <= 'z')
                stack.push((double) values.get(token));
            else {
                double oprnd1 = stack.pop();
                double oprnd2 = stack.pop();
                stack.push(calculate(oprnd1,oprnd2,token));
            }
        }
        return stack.pop();
    }
    public static void main(String[] args) {
        Map dictionary = new HashMap<>();
        dictionary.put('a',2.);
        dictionary.put('b',3.);
        dictionary.put('c',2.);
        dictionary.put('d',5.);
        dictionary.put('e',16.);
        dictionary.put('f',4.);
        dictionary.put('g',7.);
        String s = "((a+b)/(c-d)+e)*f-g";
        System.out.println(evaluatePrefix(infix2prefix(s),dictionary));
    }
}

Answer 5

If there's something about what infix and prefix mean that you don't quite understand, I'd highly suggest you reread that section of your textbook. You aren't doing yourself any favors if you come out of this with the right answer for this one problem, but still don't understand the concept.

Algorithm-wise, its pretty darn simple. You just act like a computer yourself a bit. Start by puting parens around every calculation in the order it would be calculated. Then (again in order from first calculation to last) just move the operator in front of the expression on its left hand side. After that, you can simplify by removing parens.

Answer 6

I saw this method on youtube hence posting here.

given infix expression : (a–b)/c*(d + e – f / g)

reverse it :

)g/f-e+d(*c/)b-a(

read characters from left to right.
maintain one stack for operators

 1. if character is operand add operand to the output
 2. else if character is operator or )
   2.1 while operator on top of the stack has lower or **equal** precedence than this character pop
   2.2 add the popped character to the output.
   push the character on stack

 3. else if character is parenthesis ( 
    3.1 [ same as 2 till you encounter ) . pop ) as well
 4. // no element left to read
   4.1 pop operators from stack till it is not empty
   4.2 add them to the output. 

reverse the output and print.

credits : youtube