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
- Initialize the empty stack.(astack[])
- Scan each character of the given infix expression from left to right. (theExpression.charAt(i))
- If the scanner Character is an Operand then add it to post fix string (theFinalExpression)
- If the scanned character is an operator then
- If the stack is empty, push the scanner operator int the stack.
- 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.
- 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.
- 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!
0 comments:
Post a Comment