Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

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

Posted on 2004-04-16
8
Medium Priority
?
1,833 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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
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

[Webinar] Lessons on Recovering from Petya

Skyport is working hard to help customers recover from recent attacks, like the Petya worm. This work has brought to light some important lessons. New malware attacks like this can take down your entire environment. Learn from others mistakes on how to prevent Petya like worms.

Question has a verified solution.

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

Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
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 …

597 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