5

I've been asked as a bonus programming challenge to see if braces match in a random string or char like this: {1+1} this would return 1, while {1+1}) would return 0. This is what I have so far but it doesn't seem to do anything. Any help would be great? thanks

//bonus.cpp
#include <iostream>
#include <string>
#include <queue>
#include <stack>

using namespace std;

int checkBraces (string s)
{
    //int myLength = s.length();
    std::stack<int> stack;
    char d;

    for (int i = 0; i < s.length(); i++)
    {
        char c = s[i];

        if (c == '(')
        {
            stack.push(c);
        }
        else if (c == '[') 
        {
            stack.push(c);
        }
        else if (c == '{')
        {
            stack.push(c);
        }

        else if (c == ')')
        {
            if (stack.empty())
            {
                return false;
            }
            else
            {
                d = stack.top();
                stack.pop();
                if (d != '(')
                {
                    return false;
                }
            }
        }

        else if (c == ']')
        {
            if (stack.empty())
            {
                return false;
            }
            else
            {
                d = stack.top();
                stack.pop();
                if (d != '[')
                {
                    return false;
                }
            }
        }
        else if (c == '}')
        {
            if (stack.empty())
            {
                return false;
            }
            else
            {
                d = stack.top();
                stack.pop();
                if (d != '{')
                {
                    return false;
                }
            }
        }
    }

    if (stack.empty()) return true;
    else return false;

}


int main()
{
    cout << "This program checks brace ([{}]) matching in a string." << endl;

    checkBraces ("{1+1}");

}
4
  • 2
    Did you try stepping through the code in your debugger to see what's actually going on ?
    – Paul R
    Dec 7, 2012 at 9:36
  • doesn't seem to do anything - could use more info here.
    – Karthik T
    Dec 7, 2012 at 9:37
  • You've got quite a bit of redundancy. Perhaps you should have a bool pop_if_possible(std::stack<char>, char) method so you can write if (c==')' && !pop_if_possible(stack, '(')) { return false; }
    – MSalters
    Dec 7, 2012 at 9:48
  • I've got the program to working just fine, I'm just not sure how to make it return 1 or 0 if it is matching or not matching using the actual function? Dec 7, 2012 at 9:58

4 Answers 4

6

What makes you think it doesn't do anything? It does. It checks for braces, but you're not doing anything with the return of checkBraces, which, btw, should return a bool, not an int.

Did you perhaps meant something like:

if (checkBraces ("{1+1}"))
   cout << "matching";
else
   cout << "not matching";

Pro-tip: learn how to use a debugger. You should learn how to debug before you start coding anything more than a "hello world".

5
  • "{ ( } )" is accounted for: when '}' is encountered, the top of stack will be '('.
    – MSalters
    Dec 7, 2012 at 9:45
  • @MSalters ah, that's true, I missed that. Dec 7, 2012 at 9:47
  • okay okay using your IF statement you provided me my program seems to be working pretty well. I just need to be able to prompt the user to enter a string and return 1 or 0. Which I think I can accomplish by making that method a boolean instead of an int? Dec 7, 2012 at 9:49
  • @AlanGordon no, to take user input you need std::cin (google) Dec 7, 2012 at 9:50
  • Re You should learn how to debug before you start coding anything more than a "hello world": +1 for that. +10, or even more, if I could. Sometimes it's too bad we can't "vote early, vote often" here at SO. Dec 7, 2012 at 9:52
3

As an addition to what have already been said, I would say that you could reduce the amount of code. As anyway you put chars into your stack, why not having a std::stack<char>?

You could save the braces into another string, to automatically compare it using one of the std::algorithms

const std::string openingBraces("{[(");
const std::string closingBraces("}])");

if (std::find(openingBraces.begin(), openingBraces.end(), currentChar) != openingBraces.end())
    yourStack.push(currentChar);
else if (std::find(closingBraces.begin(), closingBraces.end(), currentChar) != closingBraces.end())
{
    // check if currentChar is matching the one on top of your stack
}

I haven't written everything as it's always better to find answers by yourself.

2

Minimum you should do is to print the outcome of checkBraces.

1

but it doesn't seem to do anything

It does do something. It prints This program checks brace ([{}]) matching in a string..

You are calling checkBraces ("{1+1}") but you aren't doing anything with the returned value. Since this call can be optimized away, you are in a sense correct that your program doesn't seem to do anything.

So make it do something. Print the string that is to be tested, then print the result of the test. Once you have done that, you should test, and when you're done with that, you should test some more. Don't just test easy cases such as {i+1}. Test convoluted cases that should pass, and also test cases that should fail.

Learning how to test and learning how to debug are just as important skills (if not more important skills) as is learning how to write code.

1
  • I can't believe all I had to do was cout << checkBraces (input); My program is working great thanks. I have tested several cases Iw as just using that one as I knew it should return 1. Dec 7, 2012 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.