Stacks help

[cblack618]

Hello,

I have this assignment


For this assignment, write a program that uses a single stack to check whether a string containing braces, parentheses, and brackets is properly delimited.

Then, write another program that uses a single queue to check whether a string containing braces, parentheses, and brackets is properly delimited.

Please note that two separate programs will be submitted. One using a stack and the other using a queue.

This is the code I have and there are a few errors and I'm not sure how to fix any of this

 #include <iostream>
#include <bits/stdc++.h>

using namespace std;

//Function to check if parenthesis is balanced
bool areParenthesisBalanced(string expr)
{
	stack <char> s;
	char x;

	//Traversing the expression 
	for (int i = 0; i < expr.length(); i++)
	{
		if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{')
		{
			//Push the element into the stack
			s.push(expr[i]);
			continue;
		}

		//If current character is not opening the stack, then it must be closed and empty
		if (s.empty())
			return false;

		switch (expr[i])
		{
			case ')';

				//Store the top element in a
				x = s.top();
				s.pop();
				if (x == '{' || x == '[')
					return false;
				break;

				case'}';
					//Store the top element in b
					x = s.top();
					s.pop();
					if (x == '(' || x == '[')
						return false;
					break;
					case ']';

						//Store the top element in c
						x = s.top();
						s.pop();
						if (x == '(' || x == '{')
							return false;
						break;
		}

		}

	//Check empty stack
	retrun(s.empty());
	}

};

This is the 2nd program i have

#include <iostream>

using namespace std;

char findClosing(char c)
{
if (c == '(')
return ')';
if (c == '{')
return '}';
if (c == '[')
return ']';
return -1;
}

//function to check to see if parenthesis is balanced
bool check(char expr[], int n)
{
//bases case
if (n == 0)
return true;
if (n == 1)
return false;
if (expr[0] == ')' || expr[0] == '}' || expr[0] == ']')
return false;

//search for closing bracker for first opening bracker
char closing = findClosing(expr[0]);

int i, count = 0;
for (i = 1; i < n; i++) {
if (expr[i] == expr[0])
count++;
if (expr[i] == closing) {
if (count == 0)
break;
count--;
}
}
}

//IF we don't find a closing bracket
if (i == n)
return false;

//if closing bracket was next to open
if (i == 1)
return check(expr + 2, n - 2);

if closing bracket is in the middle
return check(expr + 1, i - 1) && check(expr + i + 1, n - i - 1);
}

int main() {
char expr[] = "[(]";
int n = strlen(expr);
if (check(expr, n))
cout << "Balanced";
else
cout << "Not balanced";
return 0;
}

[ne555]

> This is the code I have and there are a few errors
¿what errors?

> This is the 2nd program i have
I fail to see a queue there

[thmm]

There is a typo on line 57.
In your switch statement you need to replace the ; with a : after case.

There is also a logic error in the code, before you try to fix it watch this tutorial to understand the logic better.
https://www.youtube.com/watch?v=QZOLb0xHB_Q

[cblack618]

How about this ?

#include <iostream>
#include <string>
#include <stack>

using namespace std;

bool is_matching_pair(char open, char close)
{
    if (open == '[' && close == ']') return true;
    else if (open == '{' && close == '}') return true;
    else if (open == '(' && close == ')') return true;

    return false;
}
bool isParenthesisBalanced(string exp)
{
    stack<char> s;
    for (int i = 0; i < exp.length(); ++i)
    {
        // if we encounter opening braces, we push them on to the stack
        if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
            s.push(exp[i]);
        // if we encounter closing braces,
        else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
        {
            //check either if the stack is empty or the braces don't match with the opening ones :
            if (s.empty() || !is_matching_pair(s.top(), exp[i]))
                return false;
            else // if the stack is not empty or the pair matches, pop this closing one
                s.pop();
        }
    }
    return s.empty();// if we got here and the stack is empty, we matched all characters
}


int main()
{
    string expression;
    cout << "Enter a string: ";
    cin >> expression;
    if (isParenthesisBalanced(expression))
        cout << "Balanced!\n";
    else
        cout << "Not balanced!\n";
    return 0;
}

[thmm]

Looks good.

[cblack618]

It’s a two part assignment. How would I do one with a queue ?

[lastchance]

@cblack618, I thought your latest effort was too good to be true:
https://gist.github.com/mycodeschool/7207410
I'm sure your teacher can spot the minor differences to that.

[cblack618]

Your point ?

[Repeater]

Take a guess, cblack. What do you think he might be saying? Do you think he's making a witty comment about Shakespearean poetry, maybe? Could that be it?

[cblack618]

I am not a witty comment decipher

[Repeater]

He says you're cheating on your assignment. If you weren't smart enough to realise that's what he's saying, you're not smart enough for programming.

[Merch]

I kind of noticed a mistake

[Merch]

In line 5

[dhayden]

You don't need is_matching_pair(). By the time you get to the call, you know that the input is ')', ']' or '}', so line 27 can be:
if (s.empty() || s.top() != exp[i]))

[cblack618]

can someone help me finish this off ?

#include <iostream>
#include <string>
#include <stack>



using namespace std;


//Function prototype
bool isBalanced(string str);

int main() {

	string str;
	cout << "Enter a parenthesis string: " << endl;
	cin >> str;

	if (isBalanced(str))
		cout << "This is a balanced parenthesis string. " << endl;
	else
		cout << "This is not a balanced parenthesis string. " << endl;

	return 0;
}

bool isBalanced(string str) {
	stack <char> s;
	char x;

	for (int k = 0; k < str.length(); k++)
	{
		switch (str[k])
			case ')':

				//Store the top element in a
				x = s.top();
				s.pop();
				if (x == '{' || x == '[')
					return false;
				break;

			case'}':
				//Store the top element in b
				x = s.top();
				s.pop();
				if (x == '(' || x == '[')
					return false;
				break;
			case ']':

				//Store the top element in c
				x = s.top();
				s.pop();
				if (x == '(' || x == '{')
					return false;
				break;
	}
}
	
//Check empty stack
return(s.empty());
	}
};

[dhayden]

You're going backwards. Why didn't you use your previous code?

[cblack618]

Cause someone pointed out that is someone elses code and I dont want my teacher to accuse me of cheating or plaigarism

[cblack618]

Can someone help me please ?

[Duthomhas]

cblack618 wrote:

Can someone help me please ?

Apparently not.

Because cblack618 isn’t actually interested in help. He is interested in a handout.

Hasn’t anyone noticed that every single one of his threads terminate the same way?

I’m impressed some of us keep trying.

[cblack618]

1) don't be rude 2) i am not looking for a handout. I prsented code i need help with. a handout is someone doing 100 percent of the work