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

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

Разработаем программу проверки корректности арифметических выражений в алфавите {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	Отв.	Доп.