C++

Forum

 
 
Computation Using A Stack

Pages: 12
DoABarrelRoll94 (51)
Everything seems to be right except for line 46. There is a bad access error but I don't know what is causing it. Also on line 61 and line 107, there are warnings stating, "returning reference to temporary local object and "variable 'result' may be uninitialized when used here" respectively. 

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
 
#include <iostream>
#include <cctype>       //isdigit(),
#include <string>       //length(), string,
using namespace std;

bool isNumber(const char&);                 //searches for number in stack
bool opPrec(const char&);                   //operator precedence

class Node                                  //CLASS node
{
private:
    char elem;
    Node* next;
    friend class LinkedStack;
};

class LinkedStack                           //CLASS linkedstack
{
public:
    LinkedStack();                          //constructor
    void push(const char&);                 //push
    int popVal();                           //pop value
    char popOp();                           //pop operator
    const int& t();                         //returns reference of top of stack
private:
    Node* top;                              //points to top of stack
};

//LINKEDSTACK FUNCTIONS//

LinkedStack::LinkedStack()
: top(NULL){};

void LinkedStack::push(const char& e)
{
    Node* temp = new Node;
    temp->elem = e;
    temp->next = top;
    
    top = temp;
}

int LinkedStack::popVal()
{
    Node* old = top;
    top = old->next;
    
    return old->elem;
}

char LinkedStack::popOp()
{
    Node* old = top;
    top = old->next;
    
    return old->elem;
}

const int& LinkedStack::t()
{
    return top->elem;
}

//MAIN//

int main()
{
    LinkedStack valStack;
    LinkedStack opStack;
    int result;
    string exp;
    cout << "Enter a mathematical expression involving numbers and operators(+,-,*,/):\n";
    cin >> exp;
    
    for (int i = 0; i < exp.size(); i++)        //search for values and push them onto valStack
    {
        if (isNumber(exp[i]))
        {
            valStack.push(exp[i]);
        }
    }
    
    opStack.push(exp[0]);                       //push first operator onto opStack
    
    for (int i = 0; i < exp.size(); i++)
    {
        if (opPrec(exp[i]))
        {
            opStack.push(exp[i]);
        }
        else
        {
            int y = valStack.popVal();
            int x = valStack.popVal();
            char op = (opStack.popOp());
            switch (op)
            {
                case '*': result = x * y;
                    break;
                case '/': result = x / y;
                    break;
                case '+': result = x + y;
                    break;
                case '-': result = x - y;
                    break;
            }
            valStack.push(result);
        }
    }
    cout << valStack.t();

    
    return 0;
}

bool isNumber(const char& elem)
{
        if (isdigit(elem))
        {
            return true;
        }
        else
        {
            return false;
        }
}

bool opPrec(const char& elem)
{
    
    if (elem == '*' || elem == '/')
    {
        return true;
    }
    else if (elem == '+' || elem == '-')
    {
        return false;
    }
    else
    {
        return false;
    }
}
theturk1234 (148)
Ok,
You wrote:
1
2
3
4
5
6
7
 
int LinkedStack::popVal()
{
    Node* old = top;
    top = old->next;
    
    return old->elem;
}

You are returning a local variable: you must never do this.
Instead, write this:
1
2
3
4
5
6
7
 
int LinkedStack::popVal()
{
    Node* old = &top;
    top = old->next;
    char f = old->elem;
    return f;
}


And on line 107 you are using result without initializing it. You must do that by giving it a value. On line 70 you create it but do not give it a value. On some systems result will be initialized to zero, but other times it will be initialized to a garbage value.

Good luck!
DoABarrelRoll94 (51)
Hey theturk1234. I fixed both areas. However, when I tried referencing top with the '&' symbol, I would get an error saying, I can't init type Node with an rvalue of type Node.

So I rewrote function popVal and popOp without the ampersand. I have initialized result to 0.

However I'm still getting the bad access error on line 57 and 105. I'm really confused.

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
 
#include <iostream>
#include <cctype>       //isdigit(),
#include <string>       //length(), string,
using namespace std;

bool isNumber(const char&);                 //searches for number in stack
bool opPrec(const char&);                   //operator precedence

class Node                                  //CLASS node
{
private:
    int val;
    char op;
    Node * next;
    friend class LinkedStack;
};

class LinkedStack                           //CLASS linkedstack
{
public:
    LinkedStack();                          //constructor
    void pushVal(const int&);               //push value
    void pushOp(const char&);               //push operator
    int popVal();                           //pop value
    char popOp();                           //pop operator
    const int& t();                         //returns reference of top of stack
private:
    Node * top;                              //points to top of stack
};

//LINKEDSTACK FUNCTIONS//

LinkedStack::LinkedStack()
: top(NULL){};

void LinkedStack::pushVal(const int& e)
{
    Node* temp = new Node;
    temp->val = e;
    temp->next = top;
    
    top = temp;
}

void LinkedStack::pushOp(const char& e)
{
    Node* temp = new Node;
    temp->op = e;
    temp->next = top;
    
    top = temp;
}

int LinkedStack::popVal()
{
    Node* old = top;
    top = old->next;
    int e = old->val;
    return e;
}

char LinkedStack::popOp()
{
    Node* old = top;
    top = old->next;
    char e = old->op;
    return e;
}

const int& LinkedStack::t()
{
    return top->val;
}

//MAIN//

int main()
{
    LinkedStack valStack;
    LinkedStack opStack;
    int result = 0;
    string exp;
    cout << "Enter a mathematical expression involving numbers and operators(+,-,*,/):\n";
    cin >> exp;
    
    for (int i = 0; i < exp.size(); i++)        //search for values and push them onto valStack
    {
        if (isNumber(exp[i]) == true)
        {
            valStack.pushVal(exp[i]);
        }
    }
    
    opStack.pushOp(exp[0]);                       //push first operator onto opStack
    
    for (int i = 0; i < exp.size(); i++)
    {
        if (opPrec(exp[i]))
        {
            opStack.pushOp(exp[i]);
        }
        else
        {
            int y = valStack.popVal();
            int x = valStack.popVal();
            char op = (opStack.popOp());
            switch (op)
            {
                case '*': result = x * y;
                    break;
                case '/': result = x / y;
                    break;
                case '+': result = x + y;
                    break;
                case '-': result = x - y;
                    break;
            }
            valStack.pushVal(result);
        }
    }
    cout << valStack.t();

    return 0;
}

bool isNumber(const char& elem)
{
        if (isdigit(elem))
        {
            return true;
        }
        else
        {
            return false;
        }
}

bool opPrec(const char& elem)
{
    
    if (elem == '*' || elem == '/')
    {
        return true;
    }
    else if (elem == '+' || elem == '-')
    {
        return false;
    }
    else
    {
        return false;
    }
}
theturk1234 (148)
Ok DoABarrelRoll94,
Line 56 should read:
 
 
Node* old = &top;

You have to give any pointer the *address* of what you are trying to point at. Does that make sense?
Actually if you fix line 56 you should not get an error on line 105.
Does this fix the problem?
Last edited on
DoABarrelRoll94 (51)
I seem to get an error when I put the ampersand symbol before top.
AbstractionAnon (6954)
I'm not getting any errors.

I do get warnings on lines 86 and 96. The type of the loop counter (i) should be size_t, not int.
DoABarrelRoll94 (51)
I changed up my code again but now I'm getting a bad access error on lines 67 & 144. 

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
 
#include <iostream>
#include <string>
#include <cctype>

int applyOp(char, int, int);

using namespace std;

class Node
{
    int val;        //variable for operators
    char op;        //variable for operands
    Node* next;     //points to next node in list
    
    friend class LinkedStack;
};

class LinkedStack
{
    Node* top;
    Node* curr;
public:
    LinkedStack()
    {
        top = NULL;
    }
    void pushVal(const int&);
    void pushOp(const char&);
    int popVal();
    char popOp();
    int topOfValStack();
    char topOfOpStack();
    bool hasPrec(const char&, const char&);
    bool isEmpty();
};

void LinkedStack::pushVal(const int& num)
{
    Node* t = new Node;     //create new node
    int a = num - '0';      //convert charater '0' -> 0
    t->val = a;             //assign operand
    t->next = top;          //t's next points to top
    top = t;                //make t the top node
}

void LinkedStack::pushOp(const char& e)
{
    Node* t = new Node;
    t->op = e;
    t->next = top;
    top = t;
}

int LinkedStack::popVal()
{
    Node* old = top;
    top = old->next;
    delete old;
    return top->val;
}

char LinkedStack::popOp()
{
    Node* old = top;
    top = old->next;
    delete old;
    return top->op;
}

int LinkedStack::topOfValStack()
{
    return top->val;
}

char LinkedStack::topOfOpStack()
{
    return top->op;
}

bool LinkedStack::hasPrec(const char& e, const char& f)
{
    if((e == '*' || e == '/'))
    {
        return false;
    }
    else
    {
        return true;
    }
}

bool LinkedStack::isEmpty()
{
    return top == NULL;
}

int applyOp(char op, int x, int y)
{
    switch(op)
    {
        case '*': return y * x;
            break;
        case '/':
            if(x == 0)
            {
                cout << "Cannot divide by 0\n";
                return 0;
            }
            else
            {
                return y / x;
            }
            break;
        case '+': return y + x;
            break;
        case '-': return y - x;
            break;
        default:
            cout << "Expression entered incorrectly\n";
            return 0;
    }
}

int main()
{
    LinkedStack valStack;
    LinkedStack opStack;
    
    string exp;
    
    cout << "Enter an arithmetic expression including the following operators.(+, -, *, /)\n";
    cin >> exp;
    
    for(int i = 0; i < exp.size(); i++)
    {
        if(isdigit(exp[i]))
        {
            valStack.pushVal(exp[i]);
        }
        else if(exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/')
        {
            while(!opStack.isEmpty() && opStack.hasPrec(exp[i],opStack.topOfOpStack()))
            {
                valStack.pushVal(applyOp(opStack.popOp(), valStack.popVal(), valStack.popVal()));
            }
            opStack.pushOp(exp[i]);
        }
    }
    
    //After entire expression is parsed, apply remaining operations to remaining operands
    
    while(!opStack.isEmpty())
    {
        valStack.pushVal(applyOp(opStack.popOp(), valStack.popVal(), valStack.popVal()));
    }
    
    //Print top operand of valStack
    
    cout << valStack.topOfValStack();
    
    return 0;
}
Last edited on
Thomas1965 (4571)
1
2
3
4
5
6
7
 
int LinkedStack::popVal ()
{
  Node* old = top;
  top = old->next;
  delete old;
  return top->val;
}


It crashes because top == null. You reall should check your pointers before you use them.
DoABarrelRoll94 (51)
I thought I was just initiating top to NULL in 
1
2
3
4
 
LinkedStack()
    {
        top = NULL;
    }


Then when I push a value to the stack, the NULL node gets replaced with that pushed value.



EDIT: Nvm I see what you mean.
Last edited on
DoABarrelRoll94 (51)
Now when I enter user input, e.g. 3 + 4, I get -41 as a result when I want 7. I converted char to int in 
1
2
3
4
5
6
7
8
 
void LinkedStack::pushVal(const int& num)                       //push value
{
    Node* t = new Node;     //create new node
    int a = num - '0';      //convert charater '0' -> 0
    t->val = a;             //assign operand
    t->next = top;          //t's next points to top
    top = t;                //make t the top node
}
, so I don't see what could be the problem.
Thomas1965 (4571)
What is the complete new code now?
DoABarrelRoll94 (51)
This is the new code that I created last night. It seems to work when you input 2 operands but when more than 2, it produces an incorrect result. 

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
 
#include <iostream>         //cout, cin
#include <string>           //string,
#include <cctype>           //isdigit()
#include <sstream>          //stringstream, str()
using namespace std;

int prec(const char&);
int eval(int, int, char);

class Node
{
    int val;
    char op;
    Node* next;     //points to next node in list
    
    friend class LinkedStack;
};

class LinkedStack
{
    Node* top;
public:
    LinkedStack()
    {
        top = NULL;
    }
    void pushVal(int&);
    void pushOp(char&);
    void pop();
    int topVal();
    char topOp();
    bool empty();
};
void LinkedStack::pushVal(int& e)       //push value
{
    Node* t = new Node;                 //create new node
    t->val = e;
    t->next = top;                      //t's next points to top
    top = t;                            //make t the top node
}

void LinkedStack::pushOp(char& e)       //push operator
{
    Node* t = new Node;                 //create new node
    t->op = e;
    t->next = top;                      //t's next points to top
    top = t;                            //make t the top node
}

void LinkedStack::pop()                 // pop
{
    Node* old = top;
    top = old->next;
    delete old;
}

int LinkedStack::topVal()               //return top value
{
    return top->val;
}

char LinkedStack::topOp()               //return top operator
{
    return top->op;
}

bool LinkedStack::empty()               //checks if stack is empty
{
    return top == NULL;
}

int prec(const char& e)                 //check precedence of operators
{
    if((e == '*' || e == '/'))
    {
        return 2;
    }
    else if(e == '+' || e == '-')
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int eval(int op1, int op2, char op)     //evaluates expression
{
    switch(op)
    {
        case '*': return op1 * op2;
            break;
        case '/': return op1 / op2;
            break;
        case '+': return op1 + op2;
            break;
        case '-': return op1 - op2;
            break;
        default: return 0;
    }
}

int main()
{
    LinkedStack stack;
    string exp;
    stringstream output;
    
    cout << "Enter an arithmetic expression including the following operators.(+, -, *, /)\n";
    getline(cin, exp);
    
    for(int i = 0; i < exp.size(); i++)
    {
        if(exp[i] == '*' || exp[i] == '/' || exp[i] == '+' || exp[i] == '-')
        {
            while(!stack.empty() && prec(stack.topOp()) >= prec(exp[i]))
            {
                output << stack.topOp();
                stack.pop();
            }
            stack.pushOp(exp[i]);
        }
        else
        {
            output << exp[i];
        }
    }
    
    while(!stack.empty())
    {
        output << stack.topOp();
        stack.pop();
    }
    
    //EVALUATING POSTFIX EXPRESSION//
    
    LinkedStack result;
    string postfix = output.str();
    
    for(int i = 0; i < postfix.size(); i++)
    {
        if(isdigit(postfix[i]))
        {
            int value = postfix[i];
            result.pushVal(value);
        }
        else
        {
            int op2 = result.topVal() - '0';
            result.pop();
            int op1 = result.topVal() - '0';
            result.pop();
            int value = eval(op1, op2, postfix[i]);
            result.pushVal(value);
        }
    }
    cout << "The final result is " << result.topVal() << "." << endl;
    return 0;
}
Thomas1965 (4571)
I am getting a bit confused now. How is this related to your other thread?
http://www.cplusplus.com/forum/beginner/187224/
MaBunny (66)
Have a look at my example of the Stack(by the way,im making it for the same purpose,a calculator :-) ) at this webpage: http://paste.debian.net/418094/

Its incomplete though,but has many functions like you made,plus you can make one Stack obkject for char and another for int.

And its free,hav nice fun with it!!! Also pls give feedback.
DoABarrelRoll94 (51)
Hi Thomas1965. They're not related. The other thread is another project I'm working on. I think it's also the same concept though. Converting to postfix, then evaluating the postfix expression. It's just when I input multiple numbers, e.g. 3+4-5, that I get a wrong result. In the other thread, the difference is that I also have to allow the user to enter parentheses, and I get an error when that happens.
DoABarrelRoll94 (51)
Thanks for the reference MaBunny.
MaBunny (66)
Hey pal,thnx for the compliment,but there are some holes in the code.Like the try/catch block in the functions of Stack.ill update my work and give you a link.

And in the meantime try to use nullptr,not NULL in C++ and well,what others said.Also add some features like sorting and such(which i hope to add !!).

Bye!!
Thomas1965 (4571)
The problem is in converting the infix to postfix expression.
When I enter 1+2+3 the postfix string is 12+3+ and of course then the result is wrong.

I think it's better to create a function string InfixToPostfix(const string& infix) and focus completely on this. The actual calculations seems to work ok.
DoABarrelRoll94 (51)
Isn't that right?

1 would go into the output string.
stack:
output:1
+ in the stack.
stack:+
output:1
2 in the output string.
stack:+
output:12
+ is equal precedence to + so first + would be put in the output string, push + onto stack.
stack:+
output:12+
3 put in the output string.
stack:+
output:12+3
Pop + from stack and put onto output string.
stack:
output:12+3+
Thomas1965 (4571)
Yes you are right. Somehow I thought it be should 123++.
The problem must be with the stack. Somehow one of the operands became -45.
Pages: 12