Solved

C++ Program to Convert Infix to Postfix (problems with output)

Posted on 2004-04-16
8
1,453 Views
Last Modified: 2007-12-19
I am doing a homework assignment on infix to postfix conversion, i think i have it basically down, but i am having trouble with the output, when i put in x-(y*a/b-(z+d*e) +c)/f the output is  xya*bzde*+-c+/-f/ and it is supposed to be xya*b/zde*+-c+f/- i dont understand my problem, maybe i set up the prioritys wrong in precendence check, i need help with this, i have been working on this for some time now and i just cant figure it out. Here is the source code:

#include <iostream>
#include <iomanip>
#include <stack>
#include <string>

using namespace std;

//////////////////////////////////////////////////////////////////
// Purpose of Program: A C++ program that implements infix to   //
// postfix conversion. Reads in a sting consisting of infix     //
// expressions and outputs the postfix expressions.             //
//                                                              //
// Function Declarations:                                       //
//                                                              //
// Precedencecheck - (called from function convert)             //
//      checks the precedence of the characters                 //
// convert - (called from int main)                             //
//      converts infix string to postfix string                 //
// charactercheck - (called from function convert)              //
//      checks if character is operator or variable             //
// printstack - (called from int main) prints stack out.        //
//////////////////////////////////////////////////////////////////


bool precedencecheck (char character1, char character2);
void convert (const string& infix, string& postfix);
bool charactercheck (char character);
string printstack(string postfix);

int main()
{
int integer = 0;

        while (integer == 0)

        {
        string  infix,
        postfix;

        cout << endl << endl << "Enter an Infix Expression : ";
        cin >> infix;

        convert (infix, postfix);

        printstack(postfix);
        }

return 0;
}

void convert (const string& infix, string& postfix)
{

        stack<char> postfixstack;
//      stack<int>  precedence;

        char    sym,
                topsym;

        for ( int i = 0; i < infix.size(); i ++)
                {
                sym = infix[i];
                        if (charactercheck(sym))
                                postfix = postfix + sym;
                        else
                                {
                                while (( ! postfixstack.empty()) &&
                                (precedencecheck(postfixstack.top() , sym)))
                                {
                                topsym = postfixstack.top();
                                postfixstack.pop();
                                postfix = postfix + topsym;
                                }
                        if ((! postfixstack.empty()) && (sym == ')'))
                                postfixstack.pop();
                        else
                                postfixstack.push(sym);
                                }
                }
                while (! postfixstack.empty())
                {
                topsym = postfixstack.top();
                postfixstack.pop();
                postfix = postfix + topsym;
                }
}


bool charactercheck (char character)
{
        if (( character == '+') || (character == '*') || (character == '-')
        ||  ( character == '/') || (character == '(') || (character == ')'))
                return false;
        else
                return true;
}

bool precedencecheck (char character1, char character2)
{
        if ((character1 == '(') || (character2 == '('))
                return false;
        if ((character2 == ')') || (character1 == '*') || (character2 == '/'))
                return true;
        if ((character2 == '*') || (character1 == '/') || (character1 == '+') ||
           ( character2 == '-'))
                return false;
        else
                return true;
}

string printstack(string postfix)
{

        cout << endl << endl << "The Postfix conversion is : " << postfix << endl << endl;


}
0
Comment
Question by:JuanPantoja81
  • 4
  • 2
  • 2
8 Comments
 
LVL 27

Expert Comment

by:Dabas
ID: 10846000
Hi JuanPantoja81:
>  ( character == '/')

Maybe this should be (character == '//')
Dabas
0
 

Author Comment

by:JuanPantoja81
ID: 10846022
no, its a char variable and when i put that in i just get a multi-character character constant error.
0
 
LVL 27

Expert Comment

by:Dabas
ID: 10846071
JuanPantoja81:
C++ is not my forte, but it is obvious that the division character is being treated as a normal character.
As far as I remember, the / character is also used for other purposes, hence my suggestion.

Maybe it should be '\/'?
Or maybe try changing it to character == chr(47) ?

Dabas
0
 
LVL 27

Expert Comment

by:Dabas
ID: 10846098
Juan:
Looking at your code further, I am not so sure your precedencecheck function is that accurate.
I am sure your approach could be improved a lot by placing all of the operation characters in an array and check the precedence from there.
For example, what are you trying to achieve with this line:

        if ((character2 == ')') || (character1 == '*') || (character2 == '/'))
and with this one?
       if ((character2 == '*') || (character1 == '/') || (character1 == '+') ||
           ( character2 == '-'))
 
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

Author Comment

by:JuanPantoja81
ID: 10847662
how would i place all the operation characters in an array, by a for loop? how would i check the precedence? can you show me some code on how to do that?
0
 
LVL 27

Expert Comment

by:Dabas
ID: 10847838
JuanPantoja81:
AS I said, my C++ is rusty, and I do not remember how to work with arrays.

Have a look at this question, it looks to be quite similar to yours:

http://www.experts-exchange.com/Programming/Q_20916781.html "converting infix to postfix and evaluating it (also checking validity) using singly linked lists"

Dabas
0
 
LVL 2

Accepted Solution

by:
sitbon earned 500 total points
ID: 10857211
Determine precedence using "scores". Here's some pseudo-code:

function get_score( char op )
{
  score = 0;
  if ( op == '^' ) score = 9;
  else if ( op == '*' ) score = 8;
  else if ( op == '/' ) score = 7;
  else if ( op == '+' || op == '-' ) score = 6;

  if ( !score ) error();
  return score;
}

function convert()
{
       read operation as <operand><operator> (i.e. "a*b+c/d" is "a*" - "b+" - "c/" "d\0" )

       if ( !last operator ) continue;
       if ( operator == NULL ) go to Eval_Stack.

       if score(operator) <= score(last operator)
       concatenate this operand to last operand, then concatenate last operator.
       set the resulting string to the last operand. last operator = this operator.
       (i.e. if last = a and * and this = b and + then last = "ab*" and +)
       continue;

       else (if greater or equal)
       output last operand. set last operand = this one.
       push last operator.
       last operator = this one.
       continue.

       Label Eval_Stack:
       output this operand.
       pop each operator and output it, then return.
}


Tried and true. Give it a shot.
0
 
LVL 2

Expert Comment

by:sitbon
ID: 10857219
I forgot to mention, evaluate the parentheses and do my function recursively, so that parentheses are left out / prioritized separately.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Entering a date in Microsoft Access can be tricky. A typo can cause month and day to be shuffled, entering the day only causes an error, as does entering, say, day 31 in June. This article shows how an inputmask supported by code can help the user a…
Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may he…
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

863 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

27 Experts available now in Live!

Get 1:1 Help Now