6

I have this homework in Java where I have to convert an infix string without parenthesis to a postfix string. I've been tinkering with the code from two days but I haven't been able to catch the bug. Here's my code.

public class itp
{
    String exp, post;
    double res;
    int l;
    stack st;

    public itp(String s)
    {
        exp = s;
        post = "";
        l = exp.length();
        st = new stack(l);
        conv();
        calc();
        System.out.println("The postfix notation of "+exp+" is "+post);
        System.out.println("The result of "+exp+" is "+res);
    }

    public void conv()
    {
        char ch = ' ';
        char pre = ' ';
        for(int i =0;i<l;i++)
        {
            ch = exp.charAt(i);
            if("+-*/".indexOf(ch)==-1)post = post + ch;
            else
            {
                    pre = st.pop();
                    if(val(ch)>=val(pre))
                    {
                        st.push(pre);
                        st.push(ch);
                    }
                    else
                    {
                        while((val(ch)<=val(pre))&&(pre!='$'))
                        {
                            post = post + pre;
                            pre = st.pop();
                        }
                        st.push(ch);
                    }
            }
        }
        for(pre = st.pop();pre!='$';pre = st.pop())
        {
            post = post + pre;
        }
    }

    public void calc()
    {
        res = 0.0;
    }

    public int val(char c)
    {
        switch(c)
        {
            case '$' : return 0;
            case '+' : return 1;
            case '-' : return 2;
            case '*' : return 3;
            case '/' : return 4;
             default : return -1;
        }
    }
}

Here, the variables are as follows:

  • st is a character stack
  • ch is the current character
  • pre is the topmost char on the stack
  • exp is the input infix expression
  • post is the output postfix expression

The pop() methods works as expected except when the stack is empty, where it will return $. The function val() takes a char input and returns 4 for /, 3 for *. 2 for -. 1 for +. The integer l holds the length of exp.

It works well in most cases except when I give it a string like a*b-b*c+c*d-d*e where it outputs ab*bc*-cd*de*- which is the expected output without a + in the end.

Any advice would be much appreciated. This bug is making me crazy!

Here's the entire code:

public class itp
{
String exp, post;
double res;
int l;
stack st;

public itp(String s)
{
    exp = s;
    post = "";
    l = exp.length();
    st = new stack(l);
    conv();
    calc();
    System.out.println("The postfix notation of "+exp+" is "+post);
    System.out.println("The result of "+exp+" is "+res);
}

public void conv()
{
    char ch = ' ';
    char pre = ' ';
    for(int i =0;i<l;i++)
    {
        ch = exp.charAt(i);
        if("+-*/".indexOf(ch)==-1)post = post + ch;
        else
        {
                pre = st.pop();
                if(val(ch)>=val(pre))
                {
                    st.push(pre);
                    st.push(ch);
                }
                else
                {
                    while((val(ch)<=val(pre))&&(pre!='$'))
                    {
                        post = post + pre;
                        pre = st.pop();
                    }
                    st.push(ch);
                }
        }
    }
    for(pre = st.pop();pre!='$';pre = st.pop())
    {
        post = post + pre;
    }
}

public void calc()
{
    res = 0.0;
}

public int val(char c)
{
    switch(c)
    {
        case '$' : return 0;
        case '+' : return 1;
        case '-' : return 2;
        case '*' : return 3;
        case '/' : return 4;
         default : return -1;
    }
}
}

here's the stack class:

public class stack
{
char[] a;
int top,size;

public stack(int s)
{
    size = s;
    a = new char[size];
    top = -1;
}

public void push(char el)
{
    a[++top] = el;
}

public char pop()
{
    if(empty()) return '$';
    else return a[top--];
}

public boolean empty()
{
    return (top == -1);
}
}

Here's the main class

import java.util.Scanner;
class client
{
public static void main(String args[])
{
    System.out.println("Enter the expression");
    Scanner in = new Scanner(System.in);
    itp i = new itp(in.next());
}
}
Alok Mysore
  • 606
  • 3
  • 16
  • 9
    I would like to propose stopping using variable names like `st` and starting using variable names like `characterStack` – Richard Tingle Sep 26 '13 at 15:17
  • 3
    Also a complete program isn't here which makes reproducing the problem impossible – Richard Tingle Sep 26 '13 at 15:19
  • 3
    Please post your code here, not just a link to pastebin. – Bill the Lizard Sep 26 '13 at 15:25
  • 2
    The code still isn't complete, theres no code for stack or a main method that replicates the problem – Richard Tingle Sep 26 '13 at 15:40
  • 4
    And please, i'm begging you, class names are ClassName, variable names are variableName and full words unless its really really nessissary not to. These are just conventions that make your code much easier to read – Richard Tingle Sep 26 '13 at 15:41
  • 1
    @RichardTingle I absolutely agree. OP should his methods better so that we can understand them. Imagine how annoying Java would be if they named their methods like `isE()` or `isC()` or `aAL()` where aAl is `addActionListener` – An SO User Sep 26 '13 at 15:45
  • @gparyani No it isn't. He isn't comparing strings. – user207421 Jan 27 '16 at 00:11

1 Answers1

7

First of all the post fix of a*b-b*c+c*d-d*e is not ab*bc*-cd*de*-+ but ab*bc*-cd*+de*-.

Secondly the mistake is in your val() function. It should instead be :

case '$' : return 0;
case '+' : return 1;
case '-' : return 1;
case '*' : return 2;
case '/' : return 2;
default : return -1;

Change it and check. It will certainly work.

Mazdak
  • 105,000
  • 18
  • 159
  • 188
Bhargav Rao
  • 50,140
  • 28
  • 121
  • 140