Infix to prefix conversion C++ Help

  • Comp Sci
  • Thread starter Kingyou123
  • Start date
  • Tags
    C++
In summary, the programmer is trying to create a infix to prefix converter and prefix to infix converter. They have used a example in their textbook, but it is for an infix to postfix conversion. They figured if they reversed the equation it would give the prefix. However, they are not sure if their idea is the right one.
  • #1
Kingyou123
98
0

Homework Statement


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:
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:
#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 statement 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++
*/
 
Physics news on Phys.org
  • #2
Kingyou123 said:
I figured if I reversed the equation it would give the prefix. Right idea?
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.
 
  • #3
Mark44 said:
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.
My professor originally had this:
Code:
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:
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:
  • #4
Kingyou123 said:
My professor originally had this:
Code:
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
Did your instructor explain what op1 and op2 were supposed to be used for, and what ch was supposed to be used for?
Kingyou123 said:
Code:
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;
}

This part makes no sense to me (In fact most of the code doesn't, either)
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?
 
  • #5
Mark44 said:
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)
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?
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
 
  • #6
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.
 
  • #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:
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;
}
 
  • #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:
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 can't convert string to char.
 
Last edited:
  • #9
Kingyou123 said:
I found a different algo in my book,View attachment 106856 View attachment 106855
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
That input doesn't tell me anything. An actual infix sample expression would be much more helpful.
Kingyou123 said:
icp and isp are
Code:
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;
}
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.
 
  • #10
Kingyou123 said:
@Mark44 , I'm confused on the void intopre part. The example uses char while my professor wants us to use strings...
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?
Kingyou123 said:
For example, I'm trying to find the length of the expression.
Code:
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 can't convert string to char.
The C++ string class has a method named length. You should be using that, not the C standard library functions.
 
  • #11
Code:
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?
 
  • #12
Some comments on your code in post #3. I have added comments with numbers that are like footnotes.
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
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:
  • #13
@Mark44
Errors with this x = S.pop(); error can assign void to char. Any soultions?
Code:
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;
}
 
  • #14
Kingyou123 said:
Errors with this x = S.pop(); error can assign void to char. Any soultions?
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?
 
  • #15
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.
 

Related to Infix to prefix conversion C++ Help

What is infix to prefix conversion in C++?

Infix to prefix conversion in C++ is a process of rearranging mathematical expressions written in infix notation (with operators between operands) into prefix notation (with operators before operands). This conversion is necessary for some algorithms and programming languages that use prefix notation for evaluating mathematical expressions.

What is the algorithm for infix to prefix conversion in C++?

The algorithm for infix to prefix conversion in C++ involves using a stack data structure to store operators and parentheses, and a queue data structure to store the output. The expression is scanned from right to left, and each operand is added to the queue. When an operator is encountered, it is compared to the top of the stack. If it has higher precedence, it is pushed onto the stack. If it has lower precedence, the operators on the stack are popped and added to the queue until an operator with lower precedence is encountered. Parentheses are also handled by pushing them onto the stack and popping them when closing parentheses are encountered. The final output is the reverse of the queue, which gives the expression in prefix notation.

What are the benefits of infix to prefix conversion in C++?

Infix to prefix conversion in C++ allows for easier evaluation of mathematical expressions by computers, as prefix notation eliminates the need for parentheses and follows a strict order of operations. This can also make the code more efficient and reduce the chances of errors.

What are the limitations of infix to prefix conversion in C++?

Infix to prefix conversion in C++ may not be suitable for all applications, as some programmers may find prefix notation less intuitive and more difficult to read. Additionally, the conversion process can be time-consuming and may not be worth the effort for simpler expressions.

Can infix to prefix conversion in C++ be done manually?

Yes, infix to prefix conversion in C++ can be done manually by following the algorithm and using a pen and paper. However, it can be tedious and prone to errors, which is why it is often done using a computer program.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
986
  • Engineering and Comp Sci Homework Help
Replies
8
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
12
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
14
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
2K
Back
Top