Задача AL6
Условие
Дана конечная последовательность, состоящая из левых и правых скобок различных заданных типов. Как определить, можно ли добавить в нее цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.
Тесты
| № | Входные данные | Выходные данные |
| 1 | ( | NO |
| 2 | )) | NO |
| 3 | [} | NO |
| 4 | {} | YES |
| 5 | (){}[] | YES |
| 6 | ({[]}{}) | YES |
| 7 | [({}())[] | NO |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <string> #include <cstring> #include <cmath> using namespace std; struct stack{ char *bkt = new char; int cur; stack(){cur = 0;} void push(char x){ bkt[cur++] = x; } void pop(){ cur--; } char back(){ return bkt[cur-1]; } int size(){ return cur; } }; int main() { string brace; cin >> brace; stack x; if(brace[0] == '(' || brace[0] == '{' || brace[0] == '[') x.push(brace[0]); //Правильное выражение начинается только с открывающей скобки else{ if(brace == "") cout << "YES";//Выражение без скобок также првильное else cout << "NO"; return 0; } for(int i = 1; i < brace.length(); i++){ if(brace[i] == '(' || brace[i] == '{' || brace[i] == '['){ //Любую открывающую скобку добавляем в стек x.push(brace[i]); } else if(abs(brace[i] - x.back()) < 3 && x.size() != 0){//Модуль разницы скобок одного типа меньше трех x.pop(); } else{ cout << "NO"; return 0; } } if(x.size() == 0) cout << "YES";//Правильное арифметическое выражение получим при пустом стэке else cout << "NO"; return 0; } |
Решение
Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать структуру [latex]stack[/latex], в которую поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.
Ссылки
Код программы на ideone.com