?
Solved

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

Posted on 2004-04-16
8
Medium Priority
?
1,681 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Optimize your web performance

What's in the eBook?
- Full list of reasons for poor performance
- Ultimate measures to speed things up
- Primary web monitoring types
- KPIs you should be monitoring in order to increase your ROI

 
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
 

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 2000 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

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

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

A short article about problems I had with the new location API and permissions in Marshmallow
Today, the web development industry is booming, and many people consider it to be their vocation. The question you may be asking yourself is – how do I become a web developer?
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 …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
Suggested Courses

741 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