#URGENT# Infix to postfix conversion and evaluation problem.

Greetings!

The program works fine as long as I dont put any '(' and ')' in the infix, and I can't find the reason why is it doing that. Also, I can't seem to make the program calculate numbers bigger than 9. In terms of let's say 23+17. And after placing 23+17 in the infix, I can't seem to make postfix look like 23 17 +. Could you please help me?

Side note: My fault i started to work on that today, and i need to finish it before today 23:59 CET. So I'd be thankful if you could help me asap.

Code starts here:
----------------------------------------------------------------------

Code:

---

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
#include <ctype.h>

using namespace std;


const int size =255;
char infix[size],postfix[size],stack[size];
int top=-1;

int precedence(char ch);  // function to get the precedence of the operator
char pop();  //function to pop an element from the stack
char topelement();  // returns the top element of the stack
void push(char ch);  // pushes an element into the stack
int eval(char *postf); // evaluation of postfix

int precedence(char ch)
{
      switch(ch)
          {
              case '/' : return 4;
              case '*' : return 4;
              case '+' : return 3;
              case '-' : return 3;
              default  : return 0;
          }
}

char pop()                  //function to pop the element from the stack
{
    char ret;
    if(top!=-1)
      {  ret =stack[top];
          top--;
          return ret;
      }
    else
        return '#';
}

char topelement()          // function to return top element from the stack without popping
{
      char ch;
      if(top!=-1)
        ch=stack[top];
      else
        ch='#';
      return ch;
}

void push(char ch)          // function to push an element in the stack
{
    if(top!=size-1)
        {
            top++;
            stack[top]= ch;
        }
}


int eval(char *postf){      //Evaluation of postfix
    char *p;
    int op1,op2,result;

    p=&postf[0];
    while(*p!='\0'){

        if(isdigit(*p)){
                        push(*p-48);}
                        else{
                            op1=pop();
                            op2=pop();

            switch(*p)
            {
                case '+':
                    result = op2 + op1;
                    break;

                case '-':
                    result = op2 - op1;
                    break;

                case '/':
                    result = op2 / op1;
                    break;

                case '*':
                    result = op2 * op1;
                    break;

                default:
                    printf("\nInvalid Operator");
                    return 0;
            }
            push(result);
        }

        p++;
    }
    result=pop();
    return result;
}



//-----------------MAIN----------------------

int main()
{
    char ele,elem,st[2];
    int prep,pre,popped,j=0,chk=0,p;
    strcpy(postfix," ");

    cout<<"infix: ";
    gets(infix);

    for(int i=0;infix[i]!=0;i++){
          while(infix[i] == ' ' || infix[i] == '\t'){
              i++;
          }
          if(infix[i]!='('&&infix[i]!=')'&&infix[i]!='*'&&infix[i]!='/'&&infix[i]!='+'&&infix[i]!='-')
                      postfix[j++]=infix[i];
                  else if(infix[i]=='(')
                      {
                        elem=infix[i];
                        push(elem);
                      }
                  else if(infix[i]==')')
                      {
                        while(popped=pop() != '(')
                            postfix[j++]=popped;
                      }
                  else
                      {
                        elem=infix[i];
                        pre=precedence(elem);//stores the precedence of operator coming frm infix
                        ele=topelement();
                        prep=precedence(ele);//stores the precedence of operator at the top of the stack

                        if(pre > prep)
                          push(elem);

                        else
                          {
                                while(prep >= pre)
                                  {
                                    if(ele=='#')
                                      break;
                                    popped=pop();
                                    ele=topelement();
                                    postfix[j++]=popped;
                                    prep=precedence(ele);
                                  }
                                  push(elem);
                            }
                        }
            }

          while((popped=pop())!='#')
              postfix[j++]=popped;
          postfix[j]='\0';

          cout<<"\npost fix :"<<postfix<<endl;
          cout<<"equals: "<<eval(&postfix[0])<<endl;
          system("pause");
          return 0;
}

---

As I also reside in the CET time zone and thus am tired for obvious reasons, just a quick shot for now:

1) If the numeric entities you deal with are chars, what maximum value do you expect them to have other than 9? ;) What about int, e.g.?

2) To handle bracketed subexpressions properly you should make the infix scanner a recursive function. If you encounter a bracketed subexpression simply extract it and have the scanner call itself on that. Unfortunately, it ain't a function at all yet...

HTH

Ah, and... Welcome to CodeGuru! :)

Quote:

---

Originally Posted by Kramarz

Greetings!

The program works fine as long as I dont put any '(' and ')' in the infix, and I can't find the reason why is it doing that. Also, I can't seem to make the program calculate numbers bigger than 9.

---

The issue is that your program was written initially to process "easy", one digit, with no parenthetical expressions, and it did it by linear scanning each character and determining what to do based on that character. In other words, it is an ad-hoc, informal approach to parsing the string expression with no real structure or design to it.

There is one big problem with this approach -- you can't easily maintain this code if you need to add things like parentheses, numbers more than one digit, etc. The code will become unwieldly, and almost impossible to get right all the time. We basically would have to scrap the code you have now and rewrite it to do things formally and structured.

What should have been done is to first write a grammar that parses the expression. Then you write a parser (recursive descent is the easiest) that goes through the expression, breaks it down into tokens, and does the action based on the token and grammar rules.

The algorithm in terms of going from infix to postfix remains the same using the stack, but the big issue is how do you parse the expression properly to determine what goes on the stack? Your code has "hard-coded" the rules -- one digit, no parentheses, etc. Once you hard-code these rules into your logic, you're basically stuck with those rules.

Quote:

---

In terms of let's say 23+17. And after placing 23+17 in the infix, I can't seem to make postfix look like 23 17 +. Could you please help me?

---

How do you build the integer, when all you have is a bunch of characters? See my point above. If the string contains "10203 + 234 - (14 + 3232)", how are you going to process "10203" and interpret that as 10203? or "234" as 234? This piece of code is not going to work at all:

Code:

---

if(isdigit(*p)){
          push(*p-48);
}

---

You need to know where the string version of the integer starts and know where it ends, and then you convert that string into an int and place it on the stack. Nowhere do you do this.

If this is a school assignment (which it sounds like it is), you should have been told from the beginning that coding a formal parser is the way to handle this issue, as most assignments that require parsing a mathematical expression gives the simple grammar in what makes up an expression.

Your program inherently can only handle single digits, to add handling multiple digit numbers and parentheses is not a quick thing to do. That in itself is a huge part of your assignment which unfortunately you didn't do, and frankly may not have time to do it. If you had the time, I would have suggested you scrap this code, write the grammar rules for an expression, and write the recursive descent parser.

Regards,

Paul McKenzie

Thanks for the replies and help guys.
Looks like the ideas you gave are kinda beyond my actual knowledge.
The project is for Algorithm classes, so it doesn't check my programming knowledge. I perfectly understand how it should work, I can see that, and I can picture it in my head. But looks like the barrier is my knowledge about c++. I have no idea how I could possibly implement that in my program :(

I thought of reading the string 1 by 1, and when encountering a space (given the rule of writing in infix is to place spaces between numbers and operators), it would convert the already read string into an integer, and put it on a stack, and so on. But I have no idea how to implement that anymore :-/

I know, my fault I started so late with it, had health problems lately and other stuff to deal with meanwhile, I guess I wont pass that project class, heh.

Kind regards,
Adam.

P.s
Thanks for the welcome :)

Quote:

---

Originally Posted by Kramarz

Thanks for the replies and help guys.
Looks like the ideas you gave are kinda beyond my actual knowledge.
The project is for Algorithm classes, so it doesn't check my programming knowledge. I perfectly understand how it should work, I can see that, and I can picture it in my head. But looks like the barrier is my knowledge about c++. I have no idea how I could possibly implement that in my program :(

---

That is always an issue -- knowing what the algorithm or data structure is supposed to do is one thing -- but coding it in C++ is another thing altogether. Look how many faulty C++ linked-list attempts occur here, but the coder usually knows what a linked list is in concept.

Basically, the code would look like this in structure:

Code:

---

while (true)
{
  token_type = GetNextToken();
  if ( token_type is a number )
      place on stack
  else
    if ( token_type is an operator)
      [code to push on stack, pop stack, whatever]
    else
    if ( token_type is a left paren)
      [code to do whatever]
    else
    if (token_type is a right paren)
        [do whatever]
    else
    if ( end of expression detected )
    {
          display postfix
          break;
    }
}

---

Something like that. The GetNextToken() is what you needed to work on for your program to come close to working. That is it in a nutshell as to how you would go about solving your problem.

If you want to learn more about all of this, then a course in compiler construction is what you would take. Once you take that course, all of what I stated would make sense. Many books on this, the most famous being the "Dragon book" explains these things.

There are tools called "lex" and "yacc" that automate some of these steps. Maybe you should, in your spare time, investigate how these tools work and see how to apply them to your problem.

Regards,

Paul McKenzie