Why does my program that creates a stack using std

Question

I am creating my own stack for my data structures class. For our assignment we are using the assignment to convert a real-time infix equation into a postfix equation.
I thought my program:
took input
determines if it was digit or number(operand)
prints it out
determines if input is operator (+,-,/,*)
adds to stack or prints out, depending on stack precedence

Instead it prints out the operands as expect, but I get this error when I enter an operator

>.../dorun.sh line 33: 4136 Segmentation fault     <core dumped> sh "$<SHFILE>"


#include <vector>
using namespace std;

class DishWell{  
public:  
    char ReturnEnd(){  
        return Well.back();  
    }  
    void Push(char x){  
        Well.push_back(x);  
    }  
    void Pop(){  
        Well.pop_back();  
    }  
    bool IsEmpty(){  
        return Well.empty();  
    }  
private:  
    vector<char> Well;  
};   
#include <iostream>  
bool Precidence(char Input, char Stack){  
    int InputPrecidence,StackPrecidence;  
    switch (Input){  
        case '*':  
            InputPrecidence = 4;  
            break;
        case '/':
            InputPrecidence = 4;  
            break;  
        case '+':  
            InputPrecidence = 3;  
            break;  
        case '-':  
            InputPrecidence = 3;  
            break;  
        case '(':  
            InputPrecidence = 2;  
            break;  
        default:  
            InputPrecidence = 0;  
    }  
    switch (Stack){  
        case '*':  
            StackPrecidence = 4;  
            break;  
        case '/':  
            StackPrecidence = 4;  
            break;  
        case '+':  
            StackPrecidence = 3;  
            break;  
        case '-':  
            StackPrecidence = 3;  
            break;  
        case '(':  
            StackPrecidence = 2;  
            break;  
        default:  
            StackPrecidence = 0;  
    }  
    if(InputPrecidence>StackPrecidence) return true;  
    else return false;  
}  
int main(int argc, char** argv) {  
    DishWell DishTray;  
    char Input;  
    bool InputFlag;  
    InputFlag = true;  
    while(InputFlag){  
        cin>>Input;  
        if((((Input>='a'&&Input<='z')||(Input>='A'&&Input<='Z'))|| (Input>='0'&&Input<='9')))//If Digit or Number  
            cout<<Input;  
        if((Input=='*'||Input=='/'||Input=='+'||Input=='-')){//if operand  
            if(Precidence(Input,DishTray.ReturnEnd()))  
                DishTray.Push(Input);  
            else if(!Precidence(Input,DishTray.ReturnEnd()))  
                cout<<Input;  
        }  
        else if(!((((Input>='a'&&Input<='z')||(Input>='A'&&Input<='Z'))||    (Input>='0'&&Input<='9')))||((Input=='*'||Input=='/'||Input=='+'||Input=='-')))//if not digit/numer or operand  
            InputFlag = false;  
    }  
    while(!DishTray.IsEmpty()){  
        cout<<DishTray.ReturnEnd();  
        DishTray.Pop();  
    }  
    return 0; 

My code is very length, I know, but I appreciate help. Especially any times for efficency or future coding.

Thanks again

P.S. Dr. Zemoudeh, this is your student Macaire

Answer 1

I'll expand on Rup's answer to answer the question you didn't ask, but is more important: How can I find out where my program is crashing?

One way is to put std::cout or printf statements throughout your program. Put a statement at the beginning of every function saying, "function x enter" and at the end saying, "function x exit". Run your program and when it crashes, you'll see what function it's in. At that point, you can add lines to print the contents of each variable to find out what's going wrong.

Another way is to use a debugger, like gdb.

First, compile your program with the -g switch to enable debugging information.

linux@linux-ubuntu:~/t$ g++ prog.cpp -o prog -g

Next, tell the debugger gdb to run your program.

linux@linux-ubuntu:~/t$ gdb ./prog

At the gdb prompt, type run to start your program. I entered 4*(3+2) and the program crashed at prog.cpp:7, which is the line return Well.back();.

(gdb) run
Starting program: /home/linux/t/prog 
4*(3+2)
4
Program received signal SIGSEGV, Segmentation fault.
0x08048d0b in DishWell::ReturnEnd (this=0xbffff460) at prog.cpp:7
7           return Well.back();  

For more complex programs, you'll often need a list of all the functions that are currently being called. You can get that information with bt, short for "backtrace". In the following backtrace, you see that the function main (#1) is calling function DishWell::ReturnEnd (#0). #0 is the current function because functions form a stack, where the current function is the top of the stack (offset 0 is the top).

(gdb) bt
#0  0x08048d0b in DishWell::ReturnEnd (this=0xbffff460) at prog.cpp:7
#1  0x08048b35 in main (argc=1, argv=0xbffff534) at prog.cpp:75
(gdb) 

With only these 2 commands (run, bt), you've solved 80% of the problem: finding where your program has crashed. If you stopped reading here, you should be able to solve the problem by adding print statements or asserts to see what the state of Well is and why back() is crashing your program. But let's use gdb some more...

You can type list to see the source code around that line for more context without leaving the debugger.

(gdb) list
2   using namespace std;
3   
4   class DishWell{  
5   public:  
6       char ReturnEnd(){  
7           return Well.back();  
8       }  
9       void Push(char x){  
10          Well.push_back(x);  
11      }  
(gdb) 

gdb can print variables and simple expressions. Printing the value of Well here is not too helpful for the novice, because it's a complex data structure and not a simple variable. But we can tell gdb to call a method on that variable...

(gdb) print Well.size()
$2 = 0
(gdb) print Well.empty()
$3 = true

Ah ha, Well is empty, and you've called back() on it. When we look at some good documentation for std::vector, we see that you invoke undefined behavior, which in this case is a program crash.

Now look through your program and try to figure out why Well was empty when your program wasn't expecting it to be empty. If you like gdb, read some tutorials on it and learn how to do things like set breakpoints, or single step.

Answer 2

If I understand you correctly, your assignment is about implementing Shunting-yard algorithm.

Since, it is a data structure assignment, if I were you, I would not use std::vector. Because, it is usually not allowed. You should implement ADT, with a char stack[STACK_SIZE] or dynamically with a link list approach.

Answer 3

The error is in your while(InputFlag) loop:

    if((Input=='*'||Input=='/'||Input=='+'||Input=='-')){//if operand  
        if(Precidence(Input,DishTray.ReturnEnd()))  

The issue is that the first time through you're calling DishTray.ReturnEnd() on an empty vector. You need to check whether the vector is empty before calling Precidence and act appropriately, or return a 0 value from ReturnEnd() if the vector is empty, or something else. That all said I can't really see what you're trying to do here since you're piping the operands directly through to the output without referencing them against the stack in any way - is this really a correct implementation of the algorithm?

But you really need to learn how to debug this for yourself. You should really read dorun.sh to see how it's compiling the code, and you should find out how to use gdb or dbx or whatever debugger you have on your system to figure this out for yourself. If it's gdb, you probably want something like

 g++ -g mystack.cpp -o mystack
 gdb mystack
 run
 <enter input, e.g. 2+3+4+5>
 bt