A task: bracketed expression test

There is a text string, which contains an arbitrary bracket expression (brackets (), [], or {}). You need to create a check function(), which will check it for correctness bracket expression:

check(“Y(x)”) -> true
check(“[(]”) -> false
check(“[{}]”) -> true
check(“)(“) -> false
check(“”) -> true
check(“b([{}-()]{a})”) -> true

With the decision of the need to tinker. But when it exists – It is concise and compact (10 – 15 strings). Options there may be many solutions.

Decision

First option:

#include <iostream>
using namespace std;

const char *delim[2] = { "([{", ")]}" };

bool check(const string& s)
{
	string stack = "";
	for (int i = 0; i < s.size(); i++) {
		const char c = s[i];
		if (strchr(delim[0], c) != NULL) {
			stack.push_back(c);
			continue;
		}
		const char *z;
		if (NULL == (z = strchr(delim[1], c)))
			continue;
		if (stack.empty() || stack.back() != delim[0][z - delim[1]])
			return false;
		stack.pop_back();
	}
	return stack.empty();
}

int main()
{
	cout << check("(2 + 2) * 4") << endl;
	cout << check("(2 + 2( * 4") << endl;
	cout << check("{}") << endl;
	cout << check("]8[") << endl;
}

#include <iostream>

using namespace std;

const char *delim[2] = { "([{", ")]}" };

bool check(const string& s)

{

string stack = "";

for (int i = 0; i < s.size(); i++) {

const char c = s[i];

if (strchr(delim[0], c) != NULL) {

stack.push_back(c);

continue;

}

const char *z;

if (NULL == (z = strchr(delim[1], c)))

continue;

if (stack.empty() || stack.back() != delim[0][z - delim[1]])

return false;

stack.pop_back();

}

return stack.empty();

}

int main()

{

cout << check("(2 + 2) * 4") << endl;

cout << check("(2 + 2( * 4") << endl;

cout << check("{}") << endl;

cout << check("]8[") << endl;

}

second embodiment:

#include <iostream>
#include <vector> 
using namespace std;

const char *delim[2] = { "([{", ")]}" };

bool check(const char* p) {
	vector<char> stack(0);
	for (; *p != '\0'; p++) {
		if (strchr(delim[0], *p) != NULL) {
			stack.push_back(*p);
			continue;
		}
		const char *z;
		if (NULL == (z = strchr(delim[1], *p)))
			continue;
		if (stack.empty() ||
			stack.back() != delim[0][z - delim[1]])
			return false;
		stack.pop_back();
	}
	return stack.empty();
}

int main()
{
	cout << check("(2 + 2) * 4") << endl;
	cout << check("(2 + 2( * 4") << endl;
	cout << check("{}") << endl;
	cout << check("]8[") << endl;
}

#include <iostream>

#include <vector>

using namespace std;

const char *delim[2] = { "([{", ")]}" };

bool check(const char* p) {

vector<char> stack(0);

for (; *p != '\0'; p++) {

if (strchr(delim[0], *p) != NULL) {

stack.push_back(*p);

continue;

}

const char *z;

if (NULL == (z = strchr(delim[1], *p)))

continue;

if (stack.empty() ||

stack.back() != delim[0][z - delim[1]])

return false;

stack.pop_back();

}

return stack.empty();

}

int main()

{

cout << check("(2 + 2) * 4") << endl;

cout << check("(2 + 2( * 4") << endl;

cout << check("{}") << endl;

cout << check("]8[") << endl;

}

The result is the same:

First option:

[crayon-6766ee14b8135713099204/]

second embodiment:

[crayon-6766ee14b8141208768866/]

The result is the same:

13 thoughts on “A task: bracketed expression test”

Programmer_blog says:
03.09.2015 at 10:33
string str("{}{}{}"); int bct1, bct2, bct3; bool is_correct(true); for (auto c : str) { do { if (c == "(") { ++bct1; break; } if (c == ")") { --bct1; break; } if (c == "{") { ++bct2; break; } if (c == "}") { --bct2; break; } if (c == "[") { ++bct3; break; } if (c == "]") { --bct3; break; } } while (false); if (bct1 < 0 || bct2 < 0 || bct3 < 0) { is_correct = false; break; } } cout << (is_correct == false || bct1 || bct2 || bct3 ? "false" : "true");
Something like that (didn't check the code, there may be typos). Any possible- decorate and make more flexible, but the essence is the same, as in the case of one kind of brackets – the block diagram of the algorithm is here: http://pro-prof.com/archives/578
Reply
Olej says:
03.09.2015 at 14:03
> didn't check the code
And in vain ;-) …
1. instead of if (c == “(“) should if (c == ‘(‘)
well, in all such branches…
(and then only if it is compiled with the options of the C ++ 11 standard)
2. but it won't work without:
int bct1 = 0, bct2 = 0, bct3 = 0;
at least, until, as long as it (bct1, bct2, bct3) – local variables.
3. and, finally, this will never work just algorithmically, because such a bracket expression will also be perfectly correct:
string str( "( 1 [ 2 { 3 ) 4 ] }");
Reply
1. Programmer_blog says:
  04.09.2015 at 18:55
  >> because such a bracket expression will also be perfectly correct: ( 1 [ 2 { 3 ) 4 ] }
  I don't think this expression is correct.. In the conditions of the task it is written “check for correctness”. “right” you didn't formalize, the examples given in the problem do not seem to contain a single group of brackets, inside which the balance of other brackets is disturbed. Well, in general, it is not clear what is being asked (can be set) different types of brackets.
  I screwed up with quotes and variable initialization, yes. Another do while construct(false) I used it in vain, there will be no profit from it in this case.
  Bring your solution with stacks, interesting to see (I don't see any profit from them based on your description.).
  Reply
  1. Olej says:
    05.09.2015 at 11:49
    > I don't think this expression is correct..
    Here I don't think.
    And the code shown – thinks. ;-)
  2. Olej says:
    05.09.2015 at 11:51
    > Bring your solution with stacks, interesting to see
    And from the 1st for it lies under the spoiler “Decision”.
    And not even one solution…
  3. Olej says:
    05.09.2015 at 12:22
    > Well, in general, it is not clear what is being asked (can be set) different types of brackets.
    What is the correct bracket expression (and for different types of brackets too) children learn in the 4th grade of elementary school.
Olej says:
03.09.2015 at 14:15
Actually, it is in a camouflaged form the task of evaluating nested bracket expressions (how, for example, in LISP lambda expressions … or in a calculator), but specially in a very simplified formulation. In general, the problem of such calculations is solved recursively: when opening the next bracket expression – push the parameters onto the stack and call the bottom level of recursion, and at the end of bracket level processing – returning from recursive call and popping parameters and stack back.
But in this formulation of the problem, the calculation at the level of recursion is degenerate (To do nothing), so the recursion is gone, and the stack remains.
Reply
Andrew says:
26.04.2016 at 17:03
I want to develop a program for computer diagnostics of audio video radio equipment description of the program there is a window where you can write, write what we will check and the program knows all the parameters of the radio part, put the probes into the sound card and check the radio part if it is green, then the radio part is working if it is on yellow then the radio part is semi-working, i.e. change the beam if it is red, then the radio part is not working.?
Reply
1. Olej says:
  26.04.2016 at 17:25
  1. it will be a very complex program in terms of code and size
  2. just from the input of the sound card (microphone?) so you can't check – this is the input of the ADC, it can be applied voltage, but without external connect voltage source “radio detail” meaningless…
  3. even after resolving the issue with the voltage source, so you can check the parameters very few the simplest radio components: diode, some resistors … you can't check the transistor, not to mention more complex devices.
  4. such a program (even if you did it with all the limitations of possibilities) will be dependent from operating system: running under Windows will not work under Linux, if you do under linux – it will not work under FreeBSD, do it under FreeBSD – won't work under Solaris, etc..
  There are quite a lot of computer programs on the Internet. oscilloscopes, connected to the audio card input. Many of them – open source. Take the code of such programs and see how they work with audio input.
  Reply
Alexey says:
06.06.2016 at 22:18
#include "stdafx.h" #include #include #include
using namespace std;
bool check(char*, int = 0, int = 0);
int main() { cout<<boolalpha<<setw(17)<<"y(x) "<<check("y(x)",4)<<endl <<setw(17)<<"[(] "<<check("[(]",3)<<endl <<setw(17)<<"[{}] "<<check("[{}]",4)<<endl <<setw(17)<<")( "<<check(")(",2)<<endl <<setw(17)<<""<<check("")<<endl <<setw(17) << "b([{}-()]{a}) " << check("b([{}-()]{a})", 13) << endl <<setw(17)<<"(1[2{3)4]} "<<check("(1[2{3)4]}",10)<<endl;
_getch(); return 0; }
bool check(char* str, int finish, int start) { char chArray[] = "({[)}]"; bool result = true; int mult = 0;
for (int i = start; i<finish; i++) for (int q = 0; q<3; q++) if (str[i] == chArray[q]){ result = false; for (int f = i + 1; f < finish; f++) if (str[f] == chArray[q + 3]){ if (mult == 0){ result = check(str,f,(i+1)); if (!result) return false; break;} mult--;} else if (str[f] == chArray[q]) mult++;} return result; }
Reply
Alexey says:
21.11.2017 at 09:02
I am a beginner C++ programmer and the code may be unwieldy, but how did it happen.
#include "stdafx.h" #include #include
using namespace std;
//check(“y(x)”) -> true //check(“[(]”) -> false //check(“[{}]”) -> true //check(“)(“) -> false //check(“”) -> true //check(“b([{}-()]{ a })”) -> true
bool findclose(const string &data, char find = '\0', int ind = 0) { bool res = false;
if (find == '\0') return false;
for (int i = ind; i < data.length(); i++) { if (data[i] == find) return true; else { switch (data[i]) { case '{': res = findclose(data, '}', i + 1); if (res == false) return false; break; case '(': res = findclose(data, ')', i + 1); if (res == false) return false; break; case '[': res = findclose(data, ']', i + 1); if (res == false) return false; break; default: break; } } } return res; }
int main() { setlocale(LC_ALL, "Rus");
string data; char repeat = 'N'; do { cout << "==============================================" << endl; cout << "Введите строку проверки скобочного выражения: " <> data;
bool res = false;
for (int i = 0; i < data.length(); i++) { if (data[i] == '{' || data[i] == '(' || data[i] == '[') { switch (data[i]) { case '{': res = findclose(data, '}', i + 1); break; case '(': res = findclose(data, ')', i + 1); break; case '[': res = findclose(data, ']', i + 1); break; default: break; } break; } }
if (res) cout << "OK" << endl; else cout << "ERROR" << endl;
cout << "Повторить проверку? (Y-да, N-нет): " <> repeat;
} while (repeat == 'Y' || repeat == 'y');
system("pause"); return 0; }
Reply
Veronica says:
27.11.2017 at 13:36
Hello. Help, you are welcome. Describe how each line in the solution works (first option).
Reply
Michael says:
27.07.2020 at 16:55
Mastered c#:
using System;
namespace Homework5
{
class Program
{
static bool check(string text)
{
int count = 0;
char[] memory = new char[100];
foreach (char element in text)
{
switch (element)
{
case ‘{‘: memory[++count] = element; break;
case ‘(‘: memory[++count] = element; break;
case ‘[‘: memory[++count] = element; break;
case ‘}’: if (memory[count] == ‘{‘) { count–; } else { return false; }; break;
case ‘)’: if (memory[count] == ‘(‘) { count–; } else { return false; }; break;
case ‘]’: if (memory[count] == ‘[‘) { count–; } else { return false; }; break;
}
}
return count == 0 ? true : false;
}
static void Main(string[] args)
{
Console.WriteLine(check(Console.ReadLine()));
Console.ReadKey(true);
}
}
}
Reply

A task: bracketed expression test

13 thoughts on “A task: bracketed expression test”

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Statistics