Solved

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

Posted on 2004-04-16
8
1,619 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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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

The Ultimate Checklist to Optimize Your Website

Websites are getting bigger and complicated by the day. Video, images, custom fonts are all great for showcasing your product/service. But the price to pay in terms of reduced page load times and ultimately, decreased sales, can lead to some difficult decisions about what to cut.

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
In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
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 …
Introduction to Processes

707 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