I am trying to convert infix to postfix.For example : "20 + 2 * 3 + (2*8 + 5)* 4" ->20 2 3 * + 2 8 * 5 + 4 * + here is my code :
Stack<Character> s = new Stack<Character>();
String postfix = "";
boolean enter = true;
String infixExpr = "20 + 2 * 3 + (2*8 + 5)* 4";
for(int i = 0;i<infixExpr.length();i++){
if(Character.isDigit(infixExpr.charAt(i)) == true){
postfix = postfix + infixExpr.charAt(i);
}
if(infixExpr.charAt(i) == '+' || infixExpr.charAt(i) == '-'){
if(s.isEmpty() == true){
s.push(infixExpr.charAt(i));
}
else{
if(s.peek() == '*' || s.peek() == '/' || s.peek() == '+' || s.peek() == '-'){
while(s.isEmpty()== false){
postfix = postfix + s.pop();
}
s.push(infixExpr.charAt(i));
}
else{
s.push(infixExpr.charAt(i));
}
}
}
if(infixExpr.charAt(i) == '*' || infixExpr.charAt(i) == '/' ){
if(s.isEmpty() == true){
s.push(infixExpr.charAt(i));
}
else{
if(s.peek()== '+' || s.peek() == '-' || s.peek() == '('){
s.push(infixExpr.charAt(i));
}
else if(s.peek() == '*' || s.peek() == '/'){
while(s.isEmpty()== false){
postfix = postfix + s.pop();
}
s.push(infixExpr.charAt(i));
}
}
if(infixExpr.charAt(i) == '('){
s.push(infixExpr.charAt(i));
}
if(infixExpr.charAt(i) == ')'){
while(enter){
if(s.peek() == '('){
enter = false;
}
else{
postfix = postfix + s.pop();
}
}
}
}
}
As it is written at the top I suppose to get "20 2 3 * + 2 8 * 5 + 4 * +" but I get "2023*+28*+54" which is wrong and I revised the code many times and still I cant see the problem. It would be great if anybody could help.
Spaces
You are not putting any spaces on your postfix variable. You are only checking if the current character is one of the "interesting" characters (digits, operators), but not whether it's a space. As a result, if the current character is a space, you just skip it and you don't copy it to the postfix.
Since the only things that you put in the postfix are characters that you have checked, you end up with no spaces at all.
You can solve it like this:
inNumber
, set it to true at first.postfix
, check ifinNumber
is true. If so, add a space first.inNumber
to true.inNumber
to false.The idea about this
inNumber
is that digits that all belong to the same number should not have spaces between them. But if the digit is added topostfix
after we have processed an operator in the previous round, then it belongs to a new number, so there should be a space there.So basically, your digit handling code should look like:
And in every
if
that indicate an operator you should haveinNumber = false
.And every place where you add an operator to postfix should look like:
Handling parentheses
Your other problem is the handling of
()
.First, you put the code that checks for
(
and)
inside theif
for*
and/
. Of course, if the character at thei
position is*
or/
, it is not a(
or a)
so this code is never called.So you should move the
if
for parentheses outside, to the same level of theif
on numbers and operators.Also, your use of
enter
is wrong. If you have parenthesis inside parenthesis, like( 3 + ( 5 + 7 ) )
, then at the first)
you will go back all the way to the parenthesis after the5
, which is OK. But thenenter
will become false and you will not process the external pair correctly. This is also true for(3 + 5 ) * ( 7 + 2 )
because you are not settingenter
totrue
again after the beginning of the program.Instead of using
enter
, you should pop what's on the stack and check if it was a(
:Unpopped operators
Finally, you finish when you completed scanning the input. But at this point you will still have operators waiting on the stack! You have to pop them all and add to
postfix
. So after the loop you should have:Additional remarks:
if
statements, you used aswitch
statement.true
. The proper way to writeif (s.isEmpty() == true)
is justif (s.isEmpty())
, and instead ofs.isEmpty() != true
use! s.isEmpty()
.(
is matched by a)
, that every operator has two operands, and also handle negative numbers that may have a-
in the beginning.