1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infix to prefix conversion C++ Help

  1. Oct 2, 2016 #1
    1. The problem statement, all variables and given/known data
    I'm trying to create a infix to prefix converter and prefix to infix converter. I have used a example in my textbook, but it's for a infix to postfix conversion, I figured if I reversed the equation it would give the prefix. Right idea?
    2. The attempt at a solution
    Code (C):
    string infixToPrefix(string expression)
    {   //FINISH ME!!!!!!!
        stack<char> S; //holds operators
        stack<char>output; //display like in class
        string prefix = "";
        char ch;
        i = 0;
        //remember to read backwards the expression

        reverse(expression.begin(), expression.end()); //should be good
        while (expression.length != '\0')
        {
            ch = expression[i];
            i++;
            s1[0] = ch;
            s1[1] = '\0';
            if (ch >= 'a' && ch <= 'z')
            {
                s.push(s1);
            }
            else
            {
                s.pop(s2);
                s.pop(s3);
                strcpy(temp, "(");
                strcat(temp, s3);
                strcat(temp, s1);
                strcat(temp, s2);
                strcat(temp, ")");
                s.push(temp);
            }

        }
        return prefix;
    }
    Rest of the code
     
    Code (C):
    #include <iostream>
    #include <stack>
    #include <string>
    #include <cstring>
    #include <algorithm>

    using namespace std;

    string infixToPrefix(string expression);
    string prefixToInfix(string expression);
    int isp(char ch);
    int icp(char ch);
    bool isOperand(char C);
    void menuOption(int &choice);

    int main()
    {
        string expression;
        string output;
        int choice=-1;
        menuOption(choice);
        while(choice>=1){
            cin.ignore();
            switch(choice){
                //FINISH ME!!!!!!!
            case 1 :
                cout << "Enter your infix expression: " << endl;

                break;
                //Add a switch statment that is for case 1
                //case 1 is enter infix expression (for prefix)
                //get the equtation and put it into expression variable
                //call the infixToPrefix function and save the outcome in the output variable
            case 2 :
                cout << "Enter your prefix expression: " << endl;

                break;
                ///Add a switch statement htat is for case 2
                //case 2 is enter prefix expression (for infix)
                // and follow the same steps like case 1 but for prefixToInfix
            case 0:
                cout << "you have quit application \n";
            default:
                cout << "please rekey..1 for infix to prefix, 2 for prefix to infix, or 0 to quit : ";

                break;
                //Add a default function that is Not a valide choice try again
                //set choice to -1 again
                //and then call menuOption(choice)
            }
            cout<<"Outcome of Conversion:  "<<output<<endl;
            menuOption(choice);
        }
        return 0;
    }


    string prefixToInfix(string expression){
     //FINISH ME!!!!!!!

     string infix="";
     stack<string> S;
     string op1,op2,ch;
     
        return infix;
    }
    string infixToPrefix(string expression)
    {   //FINISH ME!!!!!!!
        stack<char> S; //holds operators
        stack<char>output; //display like in class
        string prefix = "";
        char ch;
        i = 0;
        //remember to read backwards the expression

        reverse(expression.begin(), expression.end()); //should be good
        while (expression.length != '\0')
        {
            ch = prefix[i];
            i++;
            s1[0] = ch;
            s1[1] = '\0';
            if (ch >= 'a' && ch <= 'z')
            {
                s.push(s1);
            }
            else
            {
                s.pop(s2);
                s.pop(s3);
                strcpy(temp, "(");
                strcat(temp, s3);
                strcat(temp, s1);
                strcat(temp, s2);
                strcat(temp, ")");
                s.push(temp);
            }

        }
        return prefix;
    }

    void menuOption(int &choice){

        cout<<"\n\n===Menu=== \n";
        //FINISH ME!!!!!!!
        cout << " 1. Infix to prefix Conversion \n 2. Prefix to Infix Conversion \n 0 to quit \n";
        //Look at the example output to know how to finish up this menu
        cout<<"Choice: ";
        cin >> choice;
    }

    bool isOperand(char C)
    {
        if(C >= '0' && C <= '9') return true;
        if(C >= 'a' && C <= 'z') return true;
        if(C >= 'A' && C <= 'Z') return true;
        return false;
    }

    int isp(char ch){
        switch(ch)
        {
            case '+':
            case '-': return 1;
            case '*':
            case '/': return 2;
            case '^': return 3;
            case '(': return 0;
        }
        return -1;
    }

    int icp(char ch){
        switch(ch)
        {
            case '+':
            case '-': return 1;
            case '*':
            case '/': return 2;
            case '^': return 3;
            case '(': return 4;
        }
        return -1;
    }
    /*
    string reverseString(string equation) // test if string is a valid return type
    {
        reverse(equation.begin(), equation.end());
        return equation;
    } //https://www.quora.com/How-can-I-reverse-a-string-or-a-sentence-in-C++
    */

     
     
  2. jcsd
  3. Oct 2, 2016 #2

    Mark44

    Staff: Mentor

    Sort of, but you're dealing with expressions, not equations. Here's a simple expression in the three forms:

    Prefix -- + 3 5
    Infix -- 3 + 5
    Postfix -- 3 5 +

    I don't have time to look at your code just now, but I will do so later on this evening.
     
  4. Oct 2, 2016 #3
    My professor originally had this:
    Code (C):
    string prefixToInfix(string expression){
    //FINISH ME!!!!!!!
    string infix="";
    stack<string> S;
    string op1,op2,ch;
        return infix;
    I changed op1 to op1[10] and this is the updated code for prefix to infix
    Code (C):

    string prefixToInfix(string expression){
    //FINISH ME!!!!!!!

    string infix="";
    stack<string> S;
    string op1[10],op2[10],op3[10],ch,temp[10];
    choice = string expression
    int i;

    for (i = strlen(expression); i >= 0; i--)
    {
         ch = expression[i];
         op1[0] = ch
         op2[1] = '\0';
         if (ch >= 'a' && ch <= 'z')
         {
             s.push(op1);
         }
         else
         {
             s.pop(op2);
             s.pop(op3);
             strcpy(temp, "(");
             strcat(temp, op2);
             strcat(temp, op1);
             strcat(temp, op3);
             strcat(temp, ")");
             s.push(temp);
         }

    }
        return infix;
    }
     
    Last edited by a moderator: Oct 2, 2016
  5. Oct 2, 2016 #4

    Mark44

    Staff: Mentor

    Did your instructor explain what op1 and op2 were supposed to be used for, and what ch was supposed to be used for?
    This part makes no sense to me (In fact most of the code doesn't, either)
    Code (C):
    if (ch >= 'a' && ch <= 'z')
         {
             s.push(op1);
         }
    Aren't op1 and op2 supposed to be numbers? I'm assuming that 'op' in the names of these variables stands for 'operand'. Why would you push something that contains letters, not numbers?
     
  6. Oct 2, 2016 #5
    My professor did not explain what op1 and op2 meant... I figured that they were string arrays or maybe option and option 2? I was using the algo that was in my book for the second part.
    20161002_184757.jpg 20161002_184804.jpg
     
  7. Oct 2, 2016 #6

    Mark44

    Staff: Mentor

    It would be easier to follow the code if there were some example input strings. Is there any information in the book that you haven't shown here? Or information in your class notes?

    Is the 2nd block of code in post #1 your work? That code has declarations and definitions for two functions -- isp() and icp(). What is their purpose? I can't tell what they're supposed to do from their names, which says that the choice of names is not good. Also, the definitions for these functions appears to be exactly the same.

    Regarding op1 and op2, I am 99% sure that they ARE NOT options. I'm reasonably sure that they are operands -- the numbers that are operated on by some mathematics operation. For example, in the infix expression 5 + 3, 5 and 3 are the operands, and + is the operator.
     
  8. Oct 2, 2016 #7
    I found a different algo in my book, 20161002_191728.jpg 20161002_191740.jpg
    Sorry for the odd format, but this one seems more similar to code that my professor wants to produce. The input would be a infix question like cin>> infix
    icp and isp are
    Code (C):
    int isp(char ch){
        switch(ch)
        {
            case '+':
            case '-': return 1;
            case '*':
            case '/': return 2;
            case '^': return 3;
            case '(': return 0;
        }
        return -1;
    }

    int icp(char ch){
        switch(ch)
        {
            case '+':
            case '-': return 1;
            case '*':
            case '/': return 2;
            case '^': return 3;
            case '(': return 4;
        }
        return -1;
    }
     
  9. Oct 2, 2016 #8
    @Mark44 , I'm confused on the void intopre part. The example uses char while my professor wants us to use strings...
    For example, I'm trying to find the length of the expression.
    Code (Text):
    cout << "Enter your prefix expression: " << endl;
                cin >> expression;
                 infixToPrefix(expression);
               cout << "Infix expression is:" << infix << endl;
    I try i= strlen(expression) -1; and I keep recving the error that you cant convert string to char.
     
    Last edited: Oct 2, 2016
  10. Oct 2, 2016 #9

    Mark44

    Staff: Mentor

    That input doesn't tell me anything. An actual infix sample expression would be much more helpful.
    On a cursory glance, these two functions seemed identical to me. However, there are slightly different in one case.
    Looking at this code tells me nothing, though. The names are inscrutable (what do isp and icp mean?), and there's not a single comment to give me any idea about what these are supposed to do.
     
  11. Oct 2, 2016 #10

    Mark44

    Staff: Mentor

    No, the code for intopre doesn't use char for its parameters. Its parameters are char arrays. There is no type named string in C, but there is a template class in C++ named string. Is that what you are saying?
    The C++ string class has a method named length. You should be using that, not the C standard library functions.
     
  12. Oct 2, 2016 #11
    Code (C):
    string infixToPrefix(string expression)
    {   //FINISH ME!!!!!!!
        stack<char> S; //holds operators
        stack<char>output; //display like in class
        string prefix = "";
        char ch , x;
        int i, j;
        i = expression.length() - 1;
        while (i!= -1)
        {
            ch= infix[i];
            i--;
            if (ch > = 'a' && ch <= 'z')
            {
                prefix[j] = ch;
                j++;
            }
            else
            {
                if (ch == '(')
                {
                    while (S.getTop()!= ')')
                    {
                        x = S.pop();
                        prefix[j] = x;
                        j++;
                    }
                    x = S.pop();
                }
                else
                {
                    while (isp(S.getTop()) > icp(ch))
                    {
                        x S.pop();
                        prefix[j] = x;
                        j++;
                    }
                    s.push(ch);
                }
            }
        }
        while (!S.isempty())
        {
            x = S.pop();
            if (x!= '#')
                prefix[j] = x;
            j++;
        }
        prefix[j] = '\0';
        reverse(prefix.begin(), prefix.end());
        return prefix;
    }
    I have done this so far, is there a way to get the top part of the stack without creating a get top function?
     
  13. Oct 2, 2016 #12

    Mark44

    Staff: Mentor

    Some comments on your code in post #3. I have added comments with numbers that are like footnotes.
    Code (C):
    string prefixToInfix(string expression){
    //FINISH ME!!!!!!!

    string infix="";
    stack<string> S;
    string op1[10],op2[10],op3[10],ch,temp[10];  // 1
    choice = string expression                             // 2
    int i;

    for (i = strlen(expression); i >= 0; i--)            // 3
    {
         ch = expression[i];
         op1[0] = ch
         op2[1] = '\0';
         if (ch >= 'a' && ch <= 'z')
         {
             s.push(op1);
         }
         else
         {
             s.pop(op2);
             s.pop(op3);
             strcpy(temp, "(");            // 4
             strcat(temp, op2);          // 5
             strcat(temp, op1);
             strcat(temp, op3);
             strcat[(temp, ")");
             s.push(temp);
         }

    }
        return infix;                        // 6
    }
    1. You are confusing C character arrays with C++ strings. op1, op2, op3, and temp are 10-element arrays of strings. IOW, each element of each of these variables is a string, not a character.
    2. Syntax error
    3. You should be using C++ string functions, not C standard library functions such as strlen().
    4. You should be using C++ string functions, not C standard library functions such as strcpy().
    5. You should be using C++ string functions, not C standard library functions such as strcat().
    6. In this code, infix was initialized to "", but never changed.

    Some code you show in post #1
    Code (C):
    string infixToPrefix(string expression)
    {   //FINISH ME!!!!!!!
        stack<char> S; //holds operators
        stack<char>output; //display like in class
        string prefix = "";
        char ch;
        i = 0;
        //remember to read backwards the expression

        reverse(expression.begin(), expression.end()); //should be good
        while (expression.length != '\0')          // 7
            ...
     
    7. Why are you comparing expression.length to the null character (i.e., '\0')? Just use 0, not '\0'.
     
    Last edited: Oct 2, 2016
  14. Oct 2, 2016 #13
    @Mark44
    Errors with this x = S.pop(); error can assign void to char. Any soultions?
    Code (C):
    string infixToPrefix(string expression)
    {   //FINISH ME!!!!!!!
        stack<char> S; //holds operators
        stack<char>output; //display like in class
        string prefix = "";
        char ch , x;
        int i, j;
        i = expression.length() - 1;
        while (i!= -1)
        {
            ch= infix[i];
            i--;
            if (ch > = 'a' && ch <= 'z')
            {
                prefix[j] = ch;
                j++;
            }
            else
            {
                if (ch == '(')
                {
                    while (S.top()!= ')')
                    {
                        x = S.pop();
                        prefix[j] = x;
                        j++;
                    }
                    x = S.pop();
                }
                else
                {
                    while (isp(S.top()) > icp(ch))
                    {
                        x = S.pop();
                        prefix[j] = x;
                        j++;
                    }
                    S.push(ch);
                }
            }
        }
        while (!S.empty())
        {
            x = S.pop();
            if (x!= '#')
                prefix[j] = x;
            j++;
        }
        prefix[j] = '\0';
        reverse(prefix.begin(), prefix.end());
        return prefix;
    }
     
  15. Oct 2, 2016 #14

    Mark44

    Staff: Mentor

    It's an error to try to pop anything from a stack that is empty. Have you push-ed anything onto the stack before you attempt to pop something off it?
     
  16. Oct 2, 2016 #15

    Mark44

    Staff: Mentor

    I'm afraid you are wasting your time on details, when much more important matters like what the input should look like is not crystal clear.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Infix to prefix conversion C++ Help
  1. C++ help (Replies: 10)

  2. C\C++ help needed (Replies: 2)

  3. Help with Conversion (Replies: 2)

Loading...