[Algorithm – Java] Jump infix expression to postfix – Java – converts infix to postfix

October 15, 2017 nguyenvanquan7826 Algorithm 5 responses

The algebraic expressions are used daily are expressed as central elements (infix). This demonstration is understandable to humans because most operators (+, -, *, /) are binary operators and their division between the two operands together. However for PC, to calculate the value of an algebraic expression of this type is not as simple as we still do. To fix that, computer to transfer the representation of algebraic expressions from the elements into a different type of prefix or suffix.

What is the prefix expression, infix and suffix

In the introductory paragraph above as you might imagine how the infix expression, which is simply the operator will be placed between two operands, This course is the double star. So based on the position of the operator, whether we can perform algebraic expressions as other? The answer is, and as mentioned, As we have three expressions prefix (prefix), infix (infix) and suffixes (postfix). Let's look a little introduction on how to perform expression prefix and suffix to better understand them.

– Prefix: The expression prefix is ​​represented by the operator set up before the operand. This demonstration is also known under the name "Polish notation" by Polish mathematician Jan Łukasiewicz invented in 1920. With this representation, instead write x y as secondary form factor, I will write xy. Depending on the priority of operators that they will be different arrangements, You can see some examples in the following sections of this introduction.

– Postfix: In contrast with the prefix, ie, the operator will be placed after the operands. This demonstration called "reverse Polish notation" or abbreviated as RPN (Reverse Polish notation), was invented in the mid-decade 1950 by a philosopher and computer scientist Charles Hamblin Australian.

Một số ví dụ:

example

Method transfer from infix expression to postfix

Priority of operators

One of the important things before starting the calculation must be the priority of the operators in the expression into. For simplicity we consider only binary operators and usually include: multiply (+),subtract (-), multiply (*), divide (/). According to the operator "*, /"Has the higher priority and the two operators" , -". Thus we have taken priority modes as follows operator:

1
2
3
4
5
public int priority(char c){        // thiet lap thu tu uu tien
        if (c == '+' || c == '-') return 1;
        else if (c == '*' || c == '/') return 2;
        else return 0;
    }

Check operator and operand

In this transformation algorithm we need a method to check whether a component of the string is not the operator or operand. Instead of using the structure or switch if lengthy and inconvenient when developing, I will use Regex to check.
Also because the input string is an algebraic expression, Should operands would consider not only the number but also letters from az and AZ.
There is one rule is that when using only letters allowed only one letter represents an operand, even when using multiple digits may be combined into one digit operands.

1
2
3
4
5
6
7
public boolean isOperator(char c){  // kiem tra xem co phai toan tu
        char operator[] = { '+', '-', '*', '/', ')', '(' };
        Arrays.sort(operator);
        if (Arrays.binarySearch(operator, c) > -1)
            return true;
        else return false;
    }

Standardize Infix expression before converting

The expression can Infix entering excess whitespace, characters inappropriate or misspelled syntax.
This section of your view normalized string in Java

Also you have to merge adjacent digits of the number (operand), separation of the operator, separated from each other by a space. These elements I would call a token.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
public String[] processString(String sMath){ // xu ly bieu thuc nhap vao thanh cac phan tu
        String s1 = "", elementMath[] = null;
        InfixToPostfix  IFP = new InfixToPostfix();
        sMath = sMath.trim();
        sMath = sMath.replaceAll("\\s+"," "); //    chuan hoa sMath
        for (int i=0; i<sMath.length(); i++){
            char c = sMath.charAt(i);//sMath.substring(i,1);
            if (!IFP.isOperator(c))
                s1 = s1 + c;
            else s1 = s1 + " " + c + " ";
        }
        s1 = s1.trim();
        s1 = s1.replaceAll("\\s+"," "); //  chuan hoa s1
        elementMath = s1.split(" "); //tach s1 thanh cac phan tu
        //System.out.println(s1);
        return elementMath;
    }

The algorithm to convert an Infix expression to seasoned Prefix:

Read each token in infix expression from left to right, with each token we perform the following steps:
– If the operand: for the output.
– If the opening parenthesis "(": entered stack
– If the closing parenthesis ")": operators take out and put in the stack output until you reach the opening parenthesis "(". (Parenthesis must be taken out of the stack)
– If the operator:
+/As long at the top of the stack is the operator and the operator precedence which equals or exceeds the current operator, the operator took it out of the stack and the output.
+/Putting the current operator on stack
After reviewing all infix expression, if the stack was then grab the token element in that place and to turn on output.

CEO: We will transfer the expression A * B C *((D-E)+F)/G from Infix form into a Postfix:
image

Install Java

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public String[] postfix(String[] elementMath){
        InfixToPostfix  IFP = new InfixToPostfix();
        String s1 = "", E[];
        Stack <String> S = new Stack <String>();
        for (int i=0; i<elementMath.length; i++){    // duyet cac phan tu
            char c = elementMath[i].charAt(0);  // c la ky tu dau tien cua moi phan tu
 
            if (!IFP.isOperator(c))         // neu c khong la toan tu
                s1 = s1 + " " + elementMath[i];     // xuat elem vao s1
            else{                       // c la toan tu
                if (c == '(') S.push(elementMath[i]);   // c la "(" -> day phan tu vao Stack
                else{
                    if (c == ')'){          // c la ")"
                        char c1;        //duyet lai cac phan tu trong Stack
                        do{
                            c1 = S.peek().charAt(0);    // c1 la ky tu dau tien cua phan tu
                            if (c1 != '(') s1 = s1 + " " + S.peek();    // trong khi c1 != "("
                            S.pop();
                        }while (c1 != '(');
                    }
                    else{
                        while (!S.isEmpty() && IFP.priority(S.peek().charAt(0)) >= IFP.priority(c)){
                        // Stack khong rong va trong khi phan tu trong Stack co do uu tien >= phan tu hien tai
                            s1 = s1 + " " + S.peek();   // xuat phan tu trong Stack ra s1
                            S.pop();
                        }
                        S.push(elementMath[i]); //  dua phan tu hien tai vao Stack
                    }
                }
            }
        }
        while (!S.isEmpty()){   // Neu Stack con phan tu thi day het vao s1
            s1 = s1 + " " + S.peek();
            S.pop();
        }
        E = s1.split(" ");  //  tach s1 thanh cac phan tu
        return E;
    }

And finally the main program:

01
02
03
04
05
06
07
08
09
10
11
public static void main(String[] agrs){
        String sMath, elementMath[] = null;
        InfixToPostfix  IFP = new InfixToPostfix();
        Scanner input = new Scanner(System.in);
        sMath = input.nextLine();                   //  nhap bieu thuc
        elementMath = IFP.processString(sMath);     //  tach bieu thuc thanh cac phan tu
        elementMath = IFP.postfix(elementMath);     //  dua cac phan tu ve dang postfix
        for (int i=0; i<elementMath.length; i++) //  xuat dang postfix
            System.out.print(elementMath[i] + " ");
        input.close();
    }

To test results are correct, you can use an online conversion service here . The website will also perform calculate the value of the expression after converting.
postfix

From here we can build a Calculate the value of the expression suffix