infix to RPN push pop trouble.

[TheJast]

Hey, i am working on assignment for my CS2 class to take an input file that is in infix and convert it into output. i have to use a separate priority function for operators. Currently my loop is only outputting the last input string and output string from my input file, and the output string is wrong. any help would be much appreciated. input and current output file are below the code blocks.

/*
***Program Goals***
1. convert infix expression to RPN.
2. Read input file into a string /done
3. use stack to convert input string into RPN output string
4. Separte push pop functions /done
5. create function to determine priority of the operators.
6. output both infix and RPN strings into output file.  /infix done 

***Algortithm***
1. Function for create stack. /done
2. functions to determine empty and full stack /done
3. functions for push and pop /done
4. Read data from input file /done
5. convert infix to rpn.
6. function to determine priority of operators // may be involved in rpn conversion, ask for clarification.
7. output infix and RPN strings to Program3RPN.ot
8. main function to call createStack and readEm functions. (personal goal keep main function as clean and short as possible.)
9. E.C. include parentheses in conversion, and add extra date to input file to be read in.
*/

#include <iostream>
#include <string>
#include <fstream>
#include <iomanip>
#include <ctype.h>

using namespace std;

const int maxstack = 20; 
const char initstack = 'z';



void createStack(char stack[], int &top)
{
    int i;
    top = -1;
    for (i = 0; i < maxstack; i++)
        stack[i] = initstack;
}

bool fullStack(int top)
{
    return top >= maxstack - 1;
}

bool emptyStack(int top)
{
    return top < 0;
}

void push(char stack[], int &top, char ch)
{
    if (!fullStack(top))
    {
        top++;
        stack[top] = ch;
    }
    else
        cout << "The stack is full, can't push" << endl;
}

char pop(char stack[], int &top)
{
    char ch = initstack;
    if (!emptyStack(top))
    {
        ch = stack[top];
        stack[top] = initstack;
        top--;
    }
    return ch;
}

int priority(char ch)
{
    switch (ch)
    {
    case '+':
        return 1;
        break;
    case '-':
        return 1;
        break;
    case '*':
        return 5;
        break;
    case '/':
        return 5;
        break;
    }
}

void readEm(char stack[], int &top, char ch)
{
    string inString, outString;
    int i, len;
    ifstream inf("Program3RPN.dat");
    ofstream outf("Program3RPN.ot");

    while (!inf.eof())
    {
        inf >> inString;
        ch = inString[i];
        outString += ch;
        len = inString.length();
        for (i = 0; i < len; i++)
        {
                ch = inString[i];
            if(ch == isalpha(i))
                outString += ch;
            else if(emptyStack(top))
                push(stack, top, ch);
            
            else if (priority(ch)== priority(stack[top]))
                push(stack, top, ch);
            
            else if(emptyStack(top))
                pop(stack, top);
                
            else if(priority(ch) <= priority(stack[top]))
                push(stack, top, ch);
        }
    }
    while (!emptyStack(top) && priority(ch) <= priority(stack[top]))
        {
            pop(stack, top);
        }    
    cout << inString << " " << outString << endl;
    outf << inString << " " << outString << endl;
    //cout << inString << " " << outString << endl;
}

int main()
{
    char ch;
    char stack[maxstack];
    int top;
    createStack(stack, top); 
    readEm(stack, top, ch);
    system("pause");
    return 0;
}

*****input
A+B+C
A+B*C
W/X-Y/Z
W+X*Y-Z
A*B*C
A-B/C
A*B-C/D
K/G/Z
Q/S*D
P*D/E*K
A+B*C/D-E
A*B-C+D/E

****output
A*B-C+D/E A?/???/??*-??
no idea why i'm getting back weird question marks in diamonds.

[Duthomhas]

Your algorithm needs more thinking. But first, here is some commentary on your code:

#include <iostream>
#include <string>
#include <fstream>
#include <iomanip>
#include <cctype>  // Use C++ includes

using namespace std;

const int maxstack = 20; 
//const char initstack = 'z';  // You do not need this



void createStack(char stack[], int &top)
{
    int i;
    top = -1;
//    for (i = 0; i < maxstack; i++)  // Or this. Unused data has no meaning.
//        stack[i] = initstack;
}

bool fullStack(int top)
{
    return top >= maxstack - 1;
}

bool emptyStack(int top)
{
    return top < 0;
}

void push(char stack[], int &top, char ch)
{
    if (!fullStack(top))
    {
        top++;
        stack[top] = ch;
    }
    else
        cout << "The stack is full, can't push" << endl;
}

char pop(char stack[], int &top)
{
    char ch = '\0';  // A good choice for an invalid char is zero. (A bad choice is 'z', since that is a valid input!)
    if (!emptyStack(top))
    {
        ch = stack[top];
//        stack[top] = initstack;
        top--;
    }
    return ch;
}

int priority(char ch)
{
    switch (ch)
    {
    case '+':
        return 1;
//        break;  // unreachable code -- you have already 'return'ed
    case '-':
        return 1;
//        break;
    case '*':
        return 5;
//        break;
    case '/':
        return 5;
//        break;
    }
    return 0;  // What happens if you get a character OTHER than the above four?
}

void readEm(char stack[], int &top) // declare local variables...
{
    char ch;                        // ... in the local context
    string inString, outString;
    int i; //, len;
    ifstream inf("Program3RPN.dat");
    ofstream outf("Program3RPN.out");

    while (inf >> inString) // Forget EOF. 'While input obtained' is correct.
    {
//        inf >> inString;
//        ch = inString[i];
//        outString += ch;
//        len = inString.length();
        for (i = 0; i < inString.length() /*len*/; i++)
        {
                ch = inString[i];
            if(isalpha(ch))  // ch is the character value you are testing for 'alphaness' here
                outString += ch;
            else if(emptyStack(top))
                push(stack, top, ch);
            
//            else if (priority(ch)== priority(stack[top]))  // you check for this below
//                push(stack, top, ch);
            
//            else if(emptyStack(top))   // you, er, already tested for this...
//                pop(stack, top);       // ... but want something DIFFERENT to happen?
                
            else if(priority(ch) >= /*<=*/ priority(stack[top]))  // see below
                push(stack, top, ch);
        }
//    } er, what?
    while (!emptyStack(top))// && priority(ch) <= priority(stack[top]))  // see below
        {
            outString += pop(stack, top);  // see below
        }    
    cout << inString << " " << outString << endl;
    outf << inString << " " << outString << endl;
    //cout << inString << " " << outString << endl;

    outString = "";  // <-- this, and...
    } // <-- here
}

int main()
{
//    char ch;
    char stack[maxstack];
    int top;
    createStack(stack, top); 
    readEm(stack, top);//, ch);
//    system("pause");
    return 0;
}

Point by point:

An unused value has no meaning. You do not need to set unused pieces of the stack to any specific value.

Why is addition priority 1 and multiplication priority 5? That looks really arbitrary. (It doesn’t really matter here, but I don’t know of any operations that will fall between addition and multiplication.)

If you return from a function, there is nothing else to break from. Also, you need to return something for all possible control paths, even if that path will never be taken (you think!).

Don’t use arguments to provide a local value.
Declare variables in as tight a scope as possible: i is only used in the loop, by the loop, hence, it belongs with the loop. That ch could also be declared in the loop as

  char ch = inString[i];
  

What remains, really, is the logic of the algorithm. You have been presented, somewhere, a good design (needs a little refinement, but it works well) to convert infix to RPN. But you have missed something. You MUST spend some time to understand it.

Here are some example infix expressions to work through to think about it:

input    output   stack
A+B*C                    input
^        A               add variable to output
 ^       A        +      add operator to empty stack
  ^      AB       +      add variable to output
   ^     AB       +*     add higher priority operator to stack
    ^    ABC      +*     add variable to output
     ^   ABC*     +      no more input: pop from stack to output
     ^   ABC*+           no more input: pop from stack to output
         
input    output   stack
A*B+C                    input
^        A               add variable to output
 ^       A        *      add operator to empty stack
  ^      AB       *      add variable to output
   ^     AB*             pop higher priority operator from stack to output
   ^     AB*      +      add operator to empty stack
    ^    AB*C     +      add variable to output
     ^   AB*C+           no more input: pop from stack to output

What you have right now is a whole lot of ‘try something and see if it works’.

Unfortunately, that never works.

Currently half of the conditions you check in your loop are checked twice, and they aren’t always the consequence! You must FIRST think of the flow, THEN program it in. The only way to get it is to work through some examples. (And examples must be chosen carefully to test edge cases.)

Notice how the last step(s) in the examples above are to pop the stack until empty. But you do that outside the loop. Hence the weird expressions. Be careful to reset ALL variables for each input.

With some minor modifications I got your program running for everything that does not include parentheses. Once you do that too, then it is time to think about how to get parentheses working.

input    output   stack     
(A+B)*C                  input
^                 (      add parenthesis operator to empty stack
 ^       A        (      add variable to output
  ^      A        (+     add operator to stack
   ^     AB       (+     add variable to output
    ^    AB+      (      pop operator(s) until...
    ^    AB+             ...matching parenthesis operator popped
     ^   AB+      *      add operator to empty stack
      ^  AB+C     *      add variable to output
       ^ AB+C*           no more input: pop from stack to output

input    output   stack
A*(B+C)                  input
^        A               add variable to output
 ^       A        *      add operator to empty stack
  ^      A        *(     add parenthesis operator to stack
   ^     AB       *(     add variable to output
    ^    AB       *(+    add operator to stack
     ^   ABC      *(+    add variable to output
      ^  ABC+     *(     pop operator(s) until...
      ^  ABC+     *      ...matching parentesis operator popped
       ^ ABC+*           no more input: pop from stack to output

Hope this helps.

[TheJast]

bro!!! you're amazing thank you so much. I understood more of that than 4 days of lecture on this topic. It's still not working exactly like I wanted but i'm so much closer.
my output RPN isn't correct, so i think there are things being left on the stack.
INFIX RPN
A+B+C ++A
A+B*C *+A
W/X-Y/Z //W
W+X*Y-Z *+W
A*B*C **A
A-B/C /-A
A*B-C/D /*A
K/G/Z //K
Q/S*D */Q
P*D/E*K */*P
A+B*C/D-E /*+A
A*B-C+D/E /*A

[dhayden]

This is actually pretty easy.
- always print the operands (letters) when you see them.
- When you see an operand (+,-,*,/), you want to push it on the stack, but first you need to to perform any previously pushed operations that have higher priority.

Handling parentheses is surprisingly easy too. Pretend that "(" is an operator with very low priority. Push it on the stack. When you see ')', pop and print operations until you pop the "(".