Viktor Demin Viktor Demin -4 years ago 126
C++ Question

C++: How to check whether same number of letters 'a' and 'b' are present in a string using a stack

I need to check if number of letters "a" is equal to number of letters "b" using stack.
So i understand logic of this task, but my code doesn't work.

Logic:

If current letter == to letter in stack (s.pop()) or stack is empty then push into stack
else pop from stack
after end of cycle check size of stack. If it is empty so number of letters is equl, else not

I already have class stack

#include <string>
#include <iostream>
#include <cstdlib> // для system
using namespace std;

class stack {
public:
stack() {
ptr = 0;
}
~stack() {}
bool push(int val) {
if (ptr >= MAXSIZE) return false;
body[ptr++] = val; return true;
}
bool pop(int *val) {
if (ptr == 0) return false;
*val = body[--ptr]; return true;
}
bool empty() {
return ptr == 0;
}

private:
enum { MAXSIZE = 100 };
int body[MAXSIZE];
int ptr; // указатель на последний элемент
};

int main()
{
stack s;

std::string str;
std::cout << "Enter your ab string ";
getline(std::cin, str);

for (int c : str) {
if (c == s.pop(&c) || s.empty()) {
s.push(c);
}
else {
s.pop(&c);
}

}
if (s.empty()) {
cout << "YES\n";
system("pause");
return 0;
}
else {
cout << "NO\n";
system("pause");
}
}


result for abab, aabb, ab 'YES'
for aaabb, aba 'NO'

Answer Source

You need a method to look at current value on top of stack without popping it:

class stack {
    ...
    int top() { // never use on an empty stack
        return body[ptr-1];
    }
    ...
};

That way you can write:

for (int c : str) {
    // short circuit evaluation ensures that top is never called on an empty stack
    if (s.empty() || (c == s.top()) {
        s.push(c);
    }
    else {
        s.pop(&c);
    }

If you cannot, you must push back the popped value if it should not have been popped:

for (int c : str) {
    int d;
    if (! s.pop(&d)) { // s was empty
        s.push(c);
    }
    else if (c == d) {
        s.push(d);     // should not have been popped
        s.push(c);      
    }
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download