Добрый день. Есть задачка, подсчитать количество непарных скобок в тексте. То есть: есть открывающая скобка, но закрывающую не поставили, следовательно она непарная.(ну это я так, просто для примера:) ). С составлением алгоритмов у меня проблемно, поэтому прошу у вас помощи в составлении пока что хотя бы алгоритма. ЯП роль не играет, но ориентируюсь на Delphi. Буду очень благодарен!
Алгоритм поиска непарных скобок
1
Спросил
Новые ответы
0
function IsBracketsHavePair(text: string): boolean;
var
counter, i: integer;
begin
result := false;
counter := 0;
for i := 1 to Lenght(text) - 1 do
begin
if text[i] = '(' then
counter := counter + 1;
if text[i] = ')' then
counter := counter - 1;
if counter < 0 then break;
end
if counter = 0 then result := true;
end
Как-то так. Писал по памяти :)
2
Вот пример на C: Пример: Проверка правильности расстановки скобок v1 Файл Main.cpp
#include "stdafx.h"
namespace mystack {
int stack_head = 0;
const int stack_max_length = 128;
char stack_holder[stack_max_length];
void error(char *message) {
printf("Error: %s", message);
abort();
}
void push(char ch) {
if (stack_head < stack_max_length)
stack_holder[stack_head++] = ch;
else
error("Stack holder is full");
}
char pop() {
if (stack_head > 0)
return stack_holder[--stack_head];
else
error("Stack is empty");
assert(false);
return 0;
}
bool is_empty() {
return stack_head == 0;
}
} // namespace mystack
// --------------------------------------------------------------------------------------
namespace string_analizer {
void error(const char *message) {
printf("Analizer error: %s", message);
abort();
}
bool is_open_bracket(char ch) {
return ch == '(' || ch == '{' || ch == '[';
}
char get_pair(char bracket) {
switch(bracket) {
case '(' : return ')';
case '{' : return '}';
case '[' : return ']';
default : error("Unknown bracket");
}
assert(false);
return 0;
}
bool is_close_bracket(char ch) {
return ch == get_pair('(') || ch == get_pair('{') || ch == get_pair('[');
}
void analize(const char *str) {
for(int i=0; str[i]!=0; i++) {
if (is_open_bracket(str[i]))
mystack::push(str[i]);
if (is_close_bracket(str[i])) {
if (mystack::is_empty())
error("Invalid balance (close bracket without open bracket)");
char ch = mystack::pop();
if (get_pair(ch) != str[i]) error("Invalid pair");
}
}
if (!mystack::is_empty())
error("Invalid balance (open bracket without close bracket)");
}
} // namespace string_analizer
// --------------------------------------------------------------------------------------
namespace sa = string_analizer;
int main(int argc, char* argv[])
{
char buf[128];
printf("Enter expression to analize: ");
scanf("%s", buf);
sa::analize(buf);
return 0;
}
Данный код не будет коррекстно работать, например при таком выражении "1+2)+(3+(4+5)". То есть, если не хватает пары скобок.
Будет:)
Нет не будет, потому что в приведенном примере количество символов "(" и ")" одинаково, а алгоритм определяет непарные скобки по несовпадению их количества.
Вывод: алгоритм свою задачу не выполняет.