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}");
}
Whenever you hit a closing bracket, search if the top of the stack is the opening bracket of the same nature. If this holds then pop the stack and continue the iteration, in the end if the stack is empty, it means all brackets are well-formed .
Step 1: Define a stack to hold brackets Step 2: Traverse the expression from left to right Step 2.1: If the character is opening bracket (, or { or [, then push it into stack Step 2.2: If the character is closing bracket ), } or ] Then pop from stack, and if the popped character is matched with the starting bracket ...
Therefore, a string containing bracket characters is said to be balanced if: A matching opening bracket occurs to the left of each corresponding closing bracket. Brackets enclosed within balanced brackets are also balanced. It does not contain any non-bracket characters.
One approach to check balanced parentheses is to use stack. Each time, when an open parentheses is encountered push it in the stack, and when closed parenthesis is encountered, match it with the top of stack and pop it. If stack is empty at the end, return Balanced otherwise, Unbalanced.
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".
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With