Infix Expression into Postfix expression in Java DSA

-- Leave a Comment
Hello here is java code to change Infix expression to PostFix expression. infix expression is the expression we understand and do algebraic manipulation using BODMAS rule. Compilers uses PostFix expression to do calculation. Here we would make use of the stack we discussed in the previous articles.

If you are beginner in Java. The block at 10 - 13 is a initialization block.
Using constructor we set the max Size and the size of array to of that maxSize.
The core of this code is the method inToPostFix() Here we could explain the Algorithm in words

  1. Initialize the empty stack.(astack[])
  2. Scan each character of the given infix expression from left to right. (theExpression.charAt(i))
  3. If the scanner Character is an Operand then add it to post fix string (theFinalExpression)
  4. If the scanned character is an operator then
    1. If the stack is empty, push the scanner operator int the stack.
    2. If the stack is not empty then compare the precedence of the operator at the top of the stack. If the precedence of scanned is less then or equal to the precedence of operator at TOS, then pop TOS and add it to postfix string and push the scanned operator into the TOS. If the precedence of the scanned operator is higher then the operator at TOS then push operator to the stack.
  5. If the scanned character is opening parenthesis then push it on to the stack and continue the above process steps until closing parenthesis is not scanned. When we get closed parenthesis then pop the operators from the stack until we reach opening parenthesis and then pop opening parenthesis from stack.
  6. The process is continued until all the characters of infix expression are scanned. and pop all the remaining operators from stack and add them in to the postfix string in the way they pop out.
Here is the code:

1
2
3
4
5
6
7
8
9
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
import java.util.Scanner;
class InToPostFix
{
 int maxSize;
 char astack[];
 int TOS;
 String theFinalExpression;
 String theExpression;
 
 {
  TOS = -1;
  theFinalExpression = "";
 }
 
 InToPostFix(int maxSize, String theExpression)
 {
  this.maxSize = maxSize;
  this.astack = new char [maxSize];
  this.theExpression = theExpression;
 }

 void inToPostFix()
 {
  for(int i = 0; i< maxSize ;i++)
  {
   char element = theExpression.charAt(i);
   if(isOperand(element))
    theFinalExpression = theFinalExpression + element;
   else if(isOperator(element))
   {
    if(stackIsEmpty())
     push(element);
    else
    {
     int a;
     a = checkThePrecedence(element);
     if(a == 3) // element is of higher precedence:w
      push(element);
     else if(astack[TOS] != '(')
     {
      char operator = pop();
      theFinalExpression = theFinalExpression + operator;
      push (element);
     }
    }
   }
   else if(element == '(')
    push(element);
   else if(element == ')')
   {
    char temp;
    while(astack[TOS] != '(')
    {
     temp = pop();
     theFinalExpression = theFinalExpression + temp;
    }
    pop();// Remove the '(' from stack
   }
  }
  //while(!(stackisEmpty())):q
  while(TOS != -1)
  {
   char temp = pop();
   theFinalExpression = theFinalExpression + temp;
  }
 }

 char pop()
 {
  char item = astack[TOS];
  TOS -= 1;
  return item;
 }
 
 int checkThePrecedence(char element)
 {
  char item = astack[TOS];
  int assign, assign2;
  if (item == '$')
   assign = 3;
  else if (item == '*' || item == '/')
   assign = 2;
  else //(item == '+' || item == '-')
   assign = 1;
  if (element == '$')
   assign2 = 3;
  else if(element == '*' || element == '/')
   assign2 = 2;
  else //(element == '+' || element == '-')
   assign2 = 1;
  if(assign2 > assign)
   return 3; // element is of higher precedence
  else if(assign2 == assign)
   return 2; // element is in same as in stack
  else //(assign2 < assign)
   return 1; // element is of lower precedence
 }

 boolean stackIsFull()
 {
  if(TOS == maxSize - 1)
   return true;
  else
   return false;
 }

 boolean stackIsEmpty()
 {
  if(TOS == - 1)
   return true;
  else
   return false;
 }
 
 void push(char element)
 {
  TOS += 1;
  astack[TOS] = element;
 }
 
 static boolean isOperand(char element)
 {
  if((element >='a' && element <='z') || (element >='A' && element <='Z'))
   return true;
  else
   return false;
 }
 
        static boolean isOperator(char element)
        {
                if(element == '+' || element == '-' || element == '*' || element == '/' || element == '$')
                        return true;
                else
                        return false;
        }

 void displayFinal()
 {
  System.out.println("The Final Exptession is:-\n" + theFinalExpression);
 }

 public static void main(String []args)
 {
  Scanner input = new Scanner(System.in);
  Scanner input2 = new Scanner(System.in);
  System.out.println("Enter the InFix expression");
  String theExpression = input.nextLine();
  int maxSize = theExpression.length();
  InToPostFix inToPostFix = new InToPostFix(maxSize, theExpression);
  inToPostFix.inToPostFix();
  inToPostFix.displayFinal();
  int option;
  int next = 1;
  while(next == 1)
  {
   System.out.println("Option:- \tTo do:\n1\tConvert another expression\n2\tExit this program");
   option = input2.nextInt();
   switch(option)
   {
    case 1:
    {
     System.out.println("Enter the InFix expression");
     theExpression = input.nextLine();
     maxSize = theExpression.length();
     InToPostFix inToPostFixOb = new InToPostFix(maxSize, theExpression);
     inToPostFixOb.inToPostFix();
     inToPostFixOb.displayFinal();
     break;
    }
    case 2:
    {
     next = 0;
     System.out.println("Thank you:)");
     break;
    }
    default:
     System.out.println("Please Enter a valid option");
   }
  }
 }
}

Here we use $ for power operation. Power has the highest precedence. We use while loop in the main function and switch case to match the options you selected and call the selected methods. If I need to explain any of the code above I will always be available in the comment section. Thank you!

Hello This is Sagar Devkota. Studying Bachelor of Software Engineering at Pokhara University, NCIT. Open Source Enthusiastic.

0 comments:

Post a Comment