Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
#include <iostream>
#include <stdexcept> // for exception
#include <string>
#include <cstddef>   // for NULL
#include <new>       // for bad_alloc
#include <stdlib.h>

using namespace std;

typedef float StackItemType;

class StackException : public logic_error
{
public:
    StackException(const string& message = "")
            : logic_error(message.c_str())
    {}
};

class Stack
{
public:

    Stack();/** Default constructor. */
    Stack(const Stack& aStack);/** Copy constructor. * @param aStack The stack to copy. */
    ~Stack(); //Destructor

    // Stack operations:
    bool isEmpty() const;
    void push(const StackItemType& newItem) throw(StackException);
    void pop() throw(StackException);
    void pop(StackItemType& stackTop) throw(StackException);
    void getTop(StackItemType& stackTop) const throw(StackException);

private:

    struct StackNode/** A node on the stack. */
    {
        StackItemType item; /** A data item on the stack. */
        StackNode    *next;/** Pointer to next node.     */
    };
    StackNode *topPtr; /** Pointer to first node in the stack. */
};

Stack::Stack() : topPtr(NULL)
{
}

// Copy constructor, Deep copy
Stack::Stack(const Stack& aStack)
{
    if (aStack.topPtr == NULL)
        topPtr = NULL;  // original list is empty

    else
    {
        // copy first node
        topPtr = new StackNode;
        topPtr->item = aStack.topPtr->item;

        // copy rest of list
        StackNode *newPtr = topPtr;    // new node pointer
        for (StackNode *origPtr = aStack.topPtr->next;
                origPtr != NULL; origPtr = origPtr->next)
        {
            newPtr->next = new StackNode;
            newPtr = newPtr->next;
            newPtr->item = origPtr->item;
        }

        newPtr->next = NULL; //tail
    }
}

Stack::~Stack()
{
    // pop until stack is empty
    while (!isEmpty())
        pop();
    // Assertion: topPtr == NULL
}

bool Stack::isEmpty() const
{
    return topPtr == NULL;
}

void Stack::push(const StackItemType& newItem) throw(StackException)
{
    // create a new node
    try
    {
        StackNode *newPtr = new StackNode;

        // set data portion  of new node
        newPtr->item = newItem;

        // insert the new node
        newPtr->next = topPtr; //newPtr->next pointer points to topPtr
        topPtr = newPtr;
    }
    catch (bad_alloc e)
    {
        throw StackException(
            "StackException: push cannot allocate memory.");
    }
}

void Stack::pop() throw(StackException)
{
    if (isEmpty())
        throw StackException("StackException: stack empty on pop");
    else
    {
        // stack is not empty; delete top
        StackNode *temp = topPtr;
        topPtr = topPtr->next;
        // return deleted node to system
        temp->next = NULL;  // safeguard, don't point anything, points to nothing
        delete temp;
    }
}

void Stack::pop(StackItemType& stackTop) throw(StackException)
{
    if (isEmpty())
        throw StackException("StackException: stack empty on pop");
    else
    {
        // stack is not empty; retrieve and delete top
        stackTop = topPtr->item;
        StackNode *temp = topPtr;
        topPtr = topPtr->next;

        // return deleted node to system
        temp->next = NULL;  // safeguard, points to nothing
        delete temp;
    }
}

void Stack::getTop(StackItemType& stackTop) const throw(StackException)
{
    if (isEmpty())
        throw StackException("StackException: stack empty on getTop");
    else
        // stack is not empty; retrieve top
        stackTop = topPtr->item;
}


// TODO: Write your code here
// Begin Question
float evalPostfixExpression (string str)
{
    Stack s;
    Stack g;

    StackItemType op1;
    StackItemType op2;
    StackItemType result;


    for(int i=0;i<str.size();i++)
    {
        if(str[i]!='+'&& str[i]!='-' && str[i]!='*'&& str[i]!='/')
        {
            cout<<str[i]<<endl;
            s.push(str[i]);
        }
        else
        {
            cout<<str[i];
            s.pop(op1);
            cout<<"op1="<<op1;
            s.pop(op2);
            cout<<"op2="<<op2;

            switch(str[i])
            {
            case '+' :
            result = op1 + op2;
            break;

            case '-' :
            result = op1 - op2;
            break;

            case '*' :
            result = op1 * op2;
            break;

            case '/' :
            result = op1 / op2;
            break;
            }

        }
         s.push(result);
    }
    return result;

}
// End Question

int main()
{
    system("title ADT Stack Application - Evaluating Postfix Expressions");

    string postfixExp;
    float result;

    cout << "Enter a postfix expression to be evaluated: ";
    getline(cin, postfixExp);

    result = evalPostfixExpression (postfixExp);

    cout << postfixExp << " = " << result << endl;

    system("pause");
    return 0;
}


i use the cout op1 and op2 to check my value, i found that it pops some unknown value that i din input, can someone explain to me what's wrong with my program?
You should try debug it yourself, pull it to pieces and then ask if you can't identify the issues.
The stack is fine. On line 168, you push the ascii value instead of the number. subtract '0' from it.
On line 198, you push result for every character in the string. This fills your stack with some 0s. You only need this when an operator is called.
This seems a little advance, but what would I know. I'm just starting to learn about compound data types.
Topic archived. No new replies allowed.