Пример проектирования трансформирующих систем

Проверка корректности арифметических выражений выполняется во многих трансформирующих системах – компиляторы, табличные процессоры, СУБД и др.

Разработаем программу проверки корректности арифметических выражений в алфавите {x, y, +, *, (,), ┤} классическим и автоматным подходами.

Алгоритмическое программирование

Автоматное программирование

Словесное описание С помощью переменной nxу будем проверять соответствие количества символов х, у и знаков + или *. С помощью переменной nс будем проверять соответствие количества скобок. Для проверки правильности сочетания символов в выражении будем запоминать предыдущий символ. В символьном массиве записано выражение. Перед началом выражения запишем пробел, а в конце – нулевой символ. В начальном состоянии nс=0, nху=0. Словесный алгоритм 1) анализ входного символа (начинаем со 2-го): - если х или у, если предыдущий символ – пробел или + или * или (, то nxу++ и переходим к п. 2, иначе выражение некорректно, переходим в конец; - если + или *, если предыдущий символ – x или у или), то nxу-- и переходим к п. 2, иначе выражение некорректно, переходим в конец; - если (, если предыдущий символ – пробел или + или * или (, то nс++ и переходим к п. 2, иначе выражение некорректно, переходим в конец; - если), если предыдущий символ – х или у или), то nс-- и переходим к п. 2, иначе выражение некорректно, переходим в конец; - если 0, если предыдущий символ – x или у или), то переходим к п. 4, иначе выражение некорректно, переходим в конец; 2) если nс<0 или nxу<0, выражение некорректно, переходим в конец; 3) переходим к п. 1; 4) если nс=0 и nxу=1, выражение корректно, иначе – некорректно.

Код программы void main (void) { char i; // счетчик вх. симв. char M[11] = “ x+у*(x+у)”; // входной массив signed char nxу=0; // для проверки х,у,+,* signed char nс=0; // для проверки скобок for(i=1;i!=11;i++) { // обр-ка вх. симв. switch (M[i]) { case ‘x’: case ‘y’: if((M[i-1]==32)||(M[i-1]==’+’)|| (M[i-1]==’*’)||(M[i-1]==’(‘)) {nxу++; break;} else goto 10; case ‘+’: case ‘*’: if((M[i-1]==’x’)||(M[i-1]==’y’)|| (M[i-1]==’)‘)) {nxу--; break;} else goto 10; case ‘(‘: if((M[i-1]==32)||(M[i-1]==’+’)|| M[i-1]==’*‘)||(M[i-1]==’(’)){nc++;break;} else goto 10; case ‘)‘: if((M[i-1]==’x’)||(M[i-1]==’y’)|| (M[i-1]==’)’)) {nc--; break;} else goto 10; case 0: if((M[i-1]==’x’)||(M[i-1]==’y’)|| (M[i-1]==’)‘)) goto 20; else goto 10; default: goto 10; } if((nc<0)||(nxy<0)) goto 10; } 10: printf(“Выражение некорректно”); goto 30; 20: if((nc==0)&&(nxy==1)) printf(“Выражение корректно”); else printf(“Выражение некорректно”); 30: }

Смоделируем автомат с магазинной (стековой) памятью, распознающий арифметические выражения. 1) Множество входных символов: {x,y,+,*,(,), ┤}. 2) Множество магазинных символов: { A, B, Ñ} 3) Множество состояний: t, является также и начальным состоянием автомата. 4) Алгоритм работы автомата. - Цепочка принимается, если при ее окончании всем левым скобкам нашлись правые, для всех арифметическим знаков нашлись соответствующие «x» или «y». - Цепочка отвергается, если: 1. Количество правых скобок превысило количество левых. 2. Количество «x» или «y» превысило количество арифметических знаков более чем на единицу. 3. Входная цепочка прочитана до конца, а левым скобкам не нашлось пары. 4. Входная цепочка прочитана до конца, а некоторым арифметическим знакам не нашлось соответствующих «x» или «y». Алгоритм работы: - Если входная головка читает «(», то в магазин заталкивается А. - Если входная головка читает «)», то из магазина выталкивается А. - Если входная головка читает «+» или «*», то в магазин заталкивается В. - Если входная головка читает «x» или «y», то из магазина выталкивается В. - Цепочка принимается, если при достижении символа ┤магазин пуст Ñ. - Цепочка отвергается, если: 1. На входе остаются правые скобки «)» или «x» или «y», а магазин пуст Ñ. 2. При достижении символа ┤ в магазине остаются символы А или В.

Стек. симв.	Входные символы
+, *	х,у	(	)	┤
А	↓В	Отв.	↓A	↑	Отв.
В	↓В	↑	↑↓A↓В	Отв.	Отв.
Ñ	↓В	Отв.	↓A	Отв.	Доп.

5. В начальном состоянии стек содержит ВÑ. В символьном массиве записано выражение. В конце запишем нулевой символ.

Код программы

void main (void) {

char i; // счетчик вх. симв.

char M[10] = “x+у*(x+у)”; // входной массив

char S[10]; // стек глубиной 10

S[9]=’B’; // инициал-я стека

S[8]=0;

for(i=0;i!=10;i++) { // обр-ка вх. симв.

switch (M[i]) {

case ‘+’:

case ‘*’: Stack_In(‘B’); break;

case ‘x’:

case ‘y’: if(S[0]==’B’) {Stack_Out(); break;}

else goto 10;

case ‘(‘: if(S[0]==’A’)||(S[0]==0))

Stack_In(‘А’);

else if(S[0]==’B’) {Stack_Out();

Stack_In(‘А’); Stack_In(‘B’);}

break;

case ‘)‘: if(S[0]==’A’) {Stack_Out(); break;}

else goto 10;

case 0: if(S[0]==0) goto 20;

else goto 10;

default: goto 10;

}

10: printf(“Выражение некорректно”); goto 30;

20: printf(“Выражение корректно”);

30:

}

Разработать программу проверки корректности списка типа а;(a;a;a;) классическим (алгоритмическим) и автоматным подходами.