Реалізація алгоритму рекурсивного спуску з прикладами на C++

Матеріал з Вікіпідручника

Вашій увазі пропонується невеличке керівництво та описання реалізації алгоритму рекурсивного спуску на мові програмування C++.

[ред.] Вступ

Незважаючи на те, що стандарт мови С++ досить широкий, деякі теми в ньому не розглядаються. Тут мається на увазі: синтаксичний аналіз виразів. Програми синтаксичного аналізу використовуються для вичислення алгебраїчних виразів, наприклад (100-23)*213. Вони досить корисні і використовуються в багатьох програмах. В цей момент синтаксичні аналізатори оточені певною загадковістю. По різним причинам процедури, використовуючись в процесі синтаксичного розбору, залишаються спадком вибраних. Дійсно багато програмістів достатньо розумних здаються перед процесом синтаксичного аналізу виразів. Насправді синтаксичний аналіз - виразів досить проста процедура. В багатьох відношеннях вона більш ніж проста задача перед програмістом. Її простота виявляється наслідком строгих правил алгебри. В цій роботі ми переглянем програму рекурсивного спуску аналізу(recursive-descent parser) і всі процедури, потрібні для аналізу, які дозволять обчислити арифметичні вирази. Однак перш тим як приступити до розробки синтаксичного аналізатору, треба зробити короткий вступ про вирази і правила їх граматичного поділу.

[ред.] Вирази

Оскільки програма синтаксичного поділу обчислює алгебраїчні вирази, необхідно ясно уявити перед собою, з яких частин складається вираз. Хоча в принципі вираз може тримати досить різноманітну інформацію, в рамках цієї роботи нас буде цікавити виключно арифметичні вирази. Для наших цілей ми переглянемо вирази з наступних компонентів.

• Числа
• Операції
• Дужки
• Змінні

В нашому синтаксичному аналізаторі символ “^” буде означати піднесення до степеня. Символ ”=” означає оператор присвоювання. Вище сказані компоненти об’єднуються у вираз, відповідний правилам алгебри. Покажемо приклади.

• 123-23
• (123-435)*334/34
• х^3-1
• x=1

… Встановимо наступні приорітети операторів.

Високий + - (унарні) ^ * /  % + - низький =

Оператори, котрі мають однаковий приорітет, обчислюються зліва на право.

В прикладах, показаних по процесу пояснення, всі змінні поначабться однією буквою. Рядкові і приписні букви не розрізняються. В першій версії аналізатора всі числові змінні приводяться до дійсного типу.

[ред.] Синтаксичний аналіз виразів: постановка задачі

На перший погляд, синтаксичний аналіз виразів здається досить простою задачею. Однак, щоб краще зрозуміти її, попробуємо порахувати вираз 10-2*3 Як відомо, результат цього виразу рівний 4. Незважаючи на то, що створити програму, яка обчислює арифметичний вираз, досить легко, відкривається проблема, як створити програму, яка працюватиме правильно. В якості першого варіанту можна написати наступну програму.

а = перший операнд
while(є операнди) {
  op = оператор
  b = другий операнд
  a = a op b
}

Ця програма дає перший операнд, оператор і другий операнд, а потім робить першу операцію, дає наступний оператор і його операнди тощо. Однак, якщо цей підхід покласти в основу всієї програми, то результатом виразу 10-2*3 буде 24(8*3), а не 4, оскільки ця процедура не бере до уваги приорітети операторів. Неможна просто перебирати оператори і операнди зліва направо, оскільки у відповідності з правилами алгебри множення має більший приорітет, ніж віднімання. Початкові програмісти часто думають, що це обмеження легко подолати, і деколи, як правило, в дуже рідких випадках, їм це вдається. Однак, якщо врахувати дужки, пінесення до степеня, змінні, унарні оператори і тому подібно, задача постає набагато складніше.

Незважаючи на то, що існує декілька способів створення програм, обчислюючи вирази, ми переглянемо лише найпростіший і зрозумілий. До речі, лише тому він частіше всього використовується. Цей метод називається рекурсивним спуском. По можливості читання цього коду ми зрозуміємо назву.

[ред.] Синтаксичний аналіз виразів

Існує багато способів синтаксичного аналізу і обчислення виразів. В рамках рекурсивного спуску виразу показуються як рекурсивні структури данних(recursive data structures). Якщо б вираз міг складатися із операцій +, -, *, / і дужок, то всі вирази можна було б визначити по наступним правилам.

вираз –> терм [+ терм] [- терм]
терм – >фактор [* фактор] [/ фактор]
фактор –> змінна, число або вираз 

Квадратні дужки містять необов’язковий елемент, а символ -> інтерпретується як “породжує”. Правила, вказані вище, часто називають породжуючими правилами (production rules), або продукціями. Слідом, визначення терм можна було б озвучити так: “Терм породжує фактор, помножений на фактор, або фактор, поділений на фактор”. Зверніть увагу на то, що породжуючи правила неявно враховуючи приорітет операцій.

Вираз:
10+5*Х

складається з двох термов: 10 і 5*X. Другий терм складається з двох факторів: 5 і Х. Ці фактори складаються з одного числа і однієї змінної.

З другої сторони, вираз

14*(7-Х)

складається з двох факторів: 14 і (7-Х). Фактори складаються з одного числа і одного виразу, закритого дужками. Вираз в дужках складається з двох термів(одного числа і однієї змінної). Цей процес виявляє базис рекурсивного спуску, що представляє собою набір взаємно рекурсивних функцій, працюючих поланцюгово і реалізуючих створених правил. На кожному кроці аналізатор рахує операції, послідовність яких визначена алгебраїчними правилами. Щоб продемонструвати, як породжені правила застосовуються для синтаксичного аналізу виразів, подивимося наступний приклад.

9/3-(100+56)

Для синтаксичного аналізу треба виконати наступні дії.

• 1.Знайти перший терм 9/3.
• 2.Знайти кожний фактор і поділити цілі числа. Результат рівний 3.
• 3. Знайти другий фактор, (100+56). В цій точці починається рекурсивний аналіз другого під виразу.
• 4. Знайти всі фактори і додати їх. Результат 156.
• 5. Повернутися з рекурсивного виклику і порахувати 156 із 3. Результат -153.

Якщо це дуже не зрозуміло, то не треба турбуватись. Справді, рекурсивний спуск виразу – досить складна концепція. Просто не забувайте дві важливі речі. По-перше, породжені правила неявно враховують приорітет операторів. По-друге, цей метод аналізу і обчислення виразу дуже схожий на спосіб, з допомогою якого люди самі обчислюють математичні вирази. Далі ми переглянемо три програми синтаксичного аналізу виразів. Перша програма аналізує і рахує вираз з дійсним типом, містима лише з констант. Потім ми переглянемо синтаксичний аналізатор, що дозволяє приймати змінні. І на закінчення третя версія аналізатора буде реалізовувала у вигляді шаблонного класу, який можна застосувати для синтаксичного аналізу виразів довільного типу.

[ред.] Клас parser

В основі програми синтаксичного аналізу виразів лежить клас parser. Перша версія цього класу приведена нижче. Наступні версії дають собою модифікацію першої.

 class parser
 {
	char *exp_ptr;
	char token[80];
	char tok_type;
	double vars[NUMBER];
 
	void eval_exp2(double &result);
	void eval_exp3(double &result);
	void eval_exp4(double &result);
	void eval_exp5(double &result);
	void eval_exp6(double &result);
 
	void atom(double &result);
	void get_token();
	void putback();
	void serror(int error);
	double find_var(char *s);
	int isdelim(char c);
 public:
	parser();
	double eval_exp(char *exp);
 }

Клас parser містить три закриті змінні-члени. Вираз є у вигляді простого рядка, на якого вказує вказівник exp_ptr. Таким чином, аналізатор обчислює вираз в стандартах ASCII-рядках. Наприклад, аналізатор вміє вичислити наступний вираз.

10-5
2*3.3/3.1415*3.3

Якщо аналіз починається з виразу, вказівник exp_ptr повинен вказувати на перший символ рядка. В процесі роботи аналізатор щитує решту частину рядка, поки не знайдеться її кінець. Призначення решти змінних-членів, token і tok_type, вказані далі. Початковою точкою аналізу є функція eval_exp(), якій треба передати вказівник на аналізуючий вираз. Функції eval_exp2() - eval_exp6() разом з функцією atom() виконує основу рекурсивного спуску. Вони реалізують породжені правила вказані вище. В наступних версіях аналізатора до нього буде добавлена функція eval_exp1(). Функція serror() призначена для обробки синтаксичних помилок, створених у виразі. Функції get_token() і isdelim() використовуються для дослідження виразу на частини.

[ред.] Розбір виразу на частини

Для того, щоб оцінити вираз, нам потрібно буде розбити його на компоненти. Ця операція є головною, то давайте подивитися на це безпосередньо. Кожен компонент виразу називається лексемою(token). Наприклад, вираз

A * B - (W + 10)

містить лексеми А, *, B, - (, W +, 10, і ). Кожна лексема представляє собою нерозділиму частину виразу. Взагалі, для синтаксичного аналізу необхідна функція, яка послідовно повертала б окремі лексеми, з яких складається вираз. Крім того, функція повинна ігнорувати пропубіли і знаки табуляції, а також виявляти кінець виразу. Функція, що дозволяє виділяти лексеми, називається - get_token. Вона є членом класу parser.

Нам також потрібно буде знати тип лексем. в нашій програмі використані тільки три типи луксем: VARIALE, NUMBER і DELIMITER. (До типу DELIMITER відноситься оператори і дужки.)

Функція Get_token() показана вище. Вона отримує наступну лексему з виразу, на який вказує вказівник exp_ptr і поміщає її в змінну token. Тип отриманої лексеми записується в змінну tok_type.

// Отримує наступну лексему.
void parser::get_token() {
  register char *tem;
  tok_type = 0;
  temp = token;
  *temp = '\0';
  if (!*exp_ptr) return; // at end of expression
    while(isspace(*exp_ptr)) ++exp_ptr; // skip over white space
  if(strchr("+-*/%^=()", *exp_ptr)) {
    tok_type = DELIMITER;
    // перехід в наступного символу 
    *temp++ = *exp_ptr++;
  } else if(isalpha(*exp_ptr)) {
    while(!isdelim(*exp_ptr)) *temp++ = *exp_ptr++;
    tok_type = VARIABLE;
  } else if (isdigit(*exp_ptr)) {
    while(!isdelim(*exp_ptr)) *temp++ = *exp_ptr++;
    tok_type = NUMBER;
  }
  *temp = '\0';
}
 
//Якщо параметр с є роздільником
// повертає значення true
int parser::isdelim(char c) {
  if(strchr(" +-/*%^=()", c) || c==9 || c=='\r' || c==0) return 1;
  return 0;
}

Придивимось до цих функцій. Після перших ініціалізацій функція get_token() перевіряє, чи не знайдено кінець файлу. Для цього вона перевіряє символ, на який вказує вказівник exp_ptr. Якщо його значення рівне нулю, то досягнуто кінець виразу. Якщо у виразі залишились ще не вилучені лексеми, функція get_token() пропускає всі ведучі роздільники. Оскільки роздільники ігноруються, вказівник exp_tpr може указувати або на число, змінну, оператор або кінець виразу. Якщо наступним символом є оператор, він повертаються як рядок, і записується в змінну token, а в змінну tok_type записується константа DELIMITER . Якщо наступний символ - буква, то припускається, що лексема є змінною. Вона повертаються у вигляді рядка і записується в змінну token, а в змінну tok_type VARIABLE. Якщо наступний символ - цифра, то зчитується все число.

Потім воно перетворюється в рядок і записується в змінну token, а в змінну tok_type записується в константа NUMBER. Нарешті, якщо наступний символ немає жодного відношення до тих типів, передбачається, що функція get_token() досягнула кінця виразу. Як заявлено раніше, щоб не запутувати код функції начисто, в ній пропущені перевірка на помилки, але декілька припущень було зроблено. Наприклад, передбачається, що вираз не може тримати нерозпізнаних символів. Також, в цій версії програми змінні можуть формувати довільну довжину, але тільки перший символ є істотний. Ви можете додати більше помилкової перевірки, орієнтуючись на потреби своїх особистих припущень.

Щоб краще зрозуміти процес розділення виразу на лексеми, розглянемо приклад.

А + 100 - (B * C) /2

Ось такі лексеми і типи повертає функція get_token() в цьому прикладі.

• Лексема *Тип лексеми
• А *VARIABLE
• + *DELIMITER
• 100 *NUMBER
• - *DELIMITER
• (
• DELIMITER
• В *VARIABLE
• *
• DELIMITER
• С *VARIABLE
• )
• DELIMITER
• / *DELIMITER
• 2 *NUMBER
• Null *Null

Пам'ятайте, що змінна token завжди зберігає рядок, що закінчується нульовим байтом, навіть якщо в ній записаний єдиний символ.

[ред.] Проста програма синтаксичного аналізу виразів

Розглянемо першу версію синтаксичного аналізатора. Він вичислює значення вирізів, складених лише з констант, операторів, дужок.

#include <iostream>
#include <cstdlib>
#include <cctype>
#include <cstring>
 
 using namespace std;
 
 enum types { DELIMITER = 1, VARIABLE, NUMBER};
 
 class parser {
 char *exp_ptr; // вказує на вираз
 char token[80]; // зберігає поточну лексему
 char tok_type; // зберігає тип лексеми
 void eval_exp2(double &result);
 void eval_exp3(double &result);
 void eval_exp4(double &result);
 void eval_exp5(double &result);
 void eval_exp6(double &result);
 void atom(double &result);
 void get_token();
 void serror(int error);
 int isdelim(char c);
 public:
 parser();
 double eval_exp(char *exp);
 };
 // конструктор
 parser::parser()
 {
 exp_ptr = NULL;
 }
 
 //відправна точка parser
 
 double parser::eval_exp(char *exp)
 {
 double result;
 exp_ptr = exp;
 get_token();
 if(!*token) {
 serror(2); 
 return 0.0;
 }
 eval_exp2(result);
 if(*token) 
 serror(0); 
 return result;
 }
 // додати або віднімати два тарма
 void parser::eval_exp2(double &result)
 {
 register char op;
 double temp;
 eval_exp3(result);
 while((op = *token) == '+' || op == '-') {
 get_token();
 eval_exp3(temp);
 switch(op) {
 case '-':
 result = result - temp;
 break;
 case '+':
 result = result + temp;
 break;
 }
 }
 }
 // перемножаємо або ділимо два фактори
 void parser::eval_exp3(double &result)
 {
 register char op;
 double temp; 
 
 eval_exp4(result);
 while((op = *token) == '*' || op == '/' || op == '%') {
 get_token();
 eval_exp4(temp);
 switch(op) {
 case '*':
 result = result * temp;
 break;
 case '/':
 result = result / temp;
 break;
 case '%':
 result = (int) result % (int) temp;
 break;
 }
 }
 }
 // степінь
 void parser::eval_exp4(double &result)
 {
 double temp, ex;
 register int t;
 
 eval_exp5(result);
 if(*token== '^') {
 get_token();
 eval_exp4(temp);
 ex = result;
 if(temp==0.0) {
 result = 1.0;
 return;
 }
 for(t=(int)temp-1; t>0; --t) result = result * (double)ex;
 }
 }
 
 // обчислення унарних операцій + або -
 void parser::eval_exp5(double &result)
 {
 register char op;
 op = 0;
 if((tok_type == DELIMITER) && *token=='+' || *token == '-') {
 op = *token;
 get_token();
 }
 eval_exp6(result);
 if(op=='-') result = -result;
 }
 
 // розпізнавання дужок
 void parser::eval_exp6(double &result)
 {
 if((*token == '(')) {
 get_token();
 eval_exp2(result);
 if(*token != ')')
 serror(1);
 get_token();
 }
 else 
 atom(result);
 }  
 
 // получаємо число
 void parser::atom(double &result)
 {
 switch(tok_type) {
 case NUMBER:
 result = atof(token);
 get_token();
 return;
 default:
 serror(0);
 }
 }
 // виводить повідомлення про помилку
 void parser::serror(int error)
 {
 static char *e[]= {
 "Syntax Error",
 "Unbalanced Parentheses",
 "No expression Present"
 };
 cout << e[error] << endl;
 }
 
 // дістає наступну лексему
 void parser::get_token()
 {
 register char *temp;
 tok_type = 0;
 temp = token;
 *temp = '\0';  
 
 if(!*exp_ptr) return; // в кінці виразу
 
 while(isspace(*exp_ptr)) ++exp_ptr; // пропуск роздільника
 
 if(strchr("+-*/%^=()", *exp_ptr)){
 tok_type = DELIMITER;
 // advance to next char
 *temp++ = *exp_ptr++;
 }
 else 	if(isalpha(*exp_ptr)) {
 while(!isdelim(*exp_ptr)) *temp++ = *exp_ptr++;
 tok_type = VARIABLE;
 }
 еlse	 if(isdigit(*exp_ptr)) {
 while(!isdelim(*exp_ptr)) *temp++ = *exp_ptr++;
 tok_type = NUMBER;
 }
 *temp = '\0';
 }
 
 // якщо параметр с - роздільник повертає значення true
 
 int parser::isdelim(char c)
 {
 if(strchr(" +-/*%^=()", c) || c==9 || c=='\r' || c==0)
 return 1;
 return 0;
 }

Ця програма синтаксичного аналізу може обробити наступні оператори: +, - *, /, %. Крім того, вона може піднести число до цілого степеня і виконати унарну операцію. Програма синтаксичного аналізу правильно обчислює баланс з дужками. Фактичне обчислення виразу реалізується взаємно рекурсивними функціями eval_exp2() - eval_exp6(), а також функцією atom(), яка повертається видобуте число. Призначення кожної функції описано у коментарях. Продемонструємо використання аналізатора.

 int main()
 {
 char expstr[80];
 
 cout << " Для закінчення введіть крапку.\n";
 
 parser ob; // створення аналізатора
 
 for(;;) 
 {
 cout << " Введіть вираз: ";
 cin.getline(expstr, 79);
 if(*expstr=='.') break;
 cout << " Відповідь: " << ob.eval_exp(expstr) << "\n\n";
 };
 return 0;
 }

Такі результати можна одержати за допомогою цієї програми.

Для закінчення введіть крапку.
Введіть вираз: 10-2*3
Відповідь: 4
Введіть вираз:: (10-2)*3
Відповідь: 24
Введіть вираз: 10/3
Відповідь: 3.33333
Введіть вираз: .

[ред.] Принцип роботи синтаксичного аналізатору

Щоб зрозуміти точно, як працює синтаксичний аналізатор, протрасуємо його до виразом. Припускайться, що exp_ptr вказує на початок виразу.)

10 - 3 * 2

При виклику функції eval_exp(), як точка входу в аналізатор, видобуває з виразу першу лексему. Якщо лексема є нуль, то функція друкує повідомлення “Вираз пустий” і повертає управління виникаючому модулю. Проте, в даному випадку, лексема містить число 10. Оскільки, перша лексема не рівна нулю, то викликається функція eval_exp2(). В результаті функція eval_exp2() викличе eval_exp3(), і eval_exp3() викличе eval_exp4(), який у свою чергу викличе eval_exp5(). Потім функція eval_exp5() перевіряє, чи є лексема унарним + чи -, і, якщо ні, викликає функцію eval_exp6(). У цей момент програми функція eval_exp6() або рекурсивно звертається до eval_exp2() (у разі якщо вираз містить дужки), або atom(), яка повертає число. Оскільки лексема не являється відкриваючою дужкою, виконується функція atom() і змінна result приймає число 10. Потім з виразу береться інша лексема відшукана, і функції повертають управління на ланцюжок. Оскільки наступна містить знак - , управління передається функції eval_exp2().

Потім трапляється дуже важливий момент. Оскільки лексема містить знак -, він зберегає в змінну op. Потім аналізатор бере наступну лексему, яка є 3, і знову починає рекурсивний спуск по ланцюжку. Спочатку, як і колись, викликається функція atom(), якаповертає значення 3. Це число присвоюється змінній result, після чого зчитується лексема *. Після чого управління повертається по ланцюгу до функції eval_exp3(), яка зчитує останню лексему, рівна числу 2. У цей момент виконується перша арифметична операція - множення 2 * 3. Результат повертається у функцію eval_exp2(), в якійвикоеується віднімання. Результатом віднімання являється число 4. Хоча, на перший погляд, процес аналізу спочатку здається складним, його перевірка на других прикладах показує, що всі функції працюють правильно.

На основі цього синтаксичного аналізатору можна скласти простий калькулятор. Однак перед тим, як застосовувати його в складніших програмах, наприклад, в базах даних, де потрібно навчитись працювати зі змінними. Саме цьому присвячено наступний пункт.

[ред.] Синтаксичний аналізатор, що працює зі змінними

Всі мови програмування, багато калькуляторів і електронні таблиці використовують змінні для запам'ятовування значень. У всіх них застосовується синтаксичний аналіз виразів, тому потрібно навчитись обробляти змінні. Щоб досягти цього, нам потрібно удосконалити наш синтаксичний аналіз виразів. Як заявлено раніше, для визначення змінних ми використовуватимемо букви від а до z. Змінні будуть запам'ятовуватися в масиві класу parser . Як наслідок, в клас parser потрібно включити новий член.

Double vars[NUMBERS];//зберігає значення змінних

Крім того, прийдеться змінити конструктор класу parser.

parser::parser() {
  int i;
  exp_ptr = NULL;
  for(i=0; i<NUMVARS; i++) 
  vars[i] = 0.0;
}

Як бачимо, ініціалізуються нулями. Крім того, нам згодиться функція, яка визначає значення змінної. Оскільки змінні називаються буквами від a до z, їх легко використовувати в якості індексів масиву vars, відраховуючи з імен змінних ASCII-код букви a. Цю операцію виконує функція-член find-var().

// повертає значення змінної
double parser::find_var(char *s) {
  if(!isalpha(*s)) {
    serror(1);
    return 0.0;
  }
  return vars[toupper(*token)-'A'];
}

Функція допускає довгі імена змінних, але враховує лишень перший їх символ. Всі можуть модифікувати її по своєму розсуду. Крім того, нам необхідно змінити функцію atom(), щоб вона могла обробляти на тільки числа, а і змінні. Тобто.

//вилучає  число або значення змінної
void parser::atom(double &result) {
  switch(tok_type) {
  case VARIABLE:
    result = find_var(token);
    get_token();
    return;
  case NUMBER:
    result = atof(token);
    get_token();
    return;
  default:
    serror(0);
  }
}

З технічної точки зору цих змінних достатньо, щоб виконати синтаксичний аналіз виразів, які містять змінні. Однак в нас ще нема функції, яка присвоює змінним їх значення. Досить часто ця операція виконується за межами синтаксичного аналізатора, але ми напишемо свій оператор присвоювання і зробимо його частиною класу parser. Це можна зробити по-різному. По-перше, можна добавити в клас parser функцію eval_ex1(). Тепер наш ланцюжок рекурсивного спуску буде починатися з неї. Це означає, що на початку синтаксичного аналізу виразів повинна викликатися функція eval_ex1(), а не функція eval_ex2(). Переглянемо визначення функції eval_ex1().

//присвоювання
void parser::eval_exp1(double &result) {
  int slot;
  char ttok_type;
  char temp_token[80];
  if(tok_type==VARIABLE) {
  // зберігає стару лексему
    strcpy(temp_token, token);
    ttok_type = tok_type;
    // знаходимо індекс змцнної
    slot = toupper(*token) - 'A';
    get_token(); 
    if(*token != '=') {
      putback(); // повертає поточну лексему
      // відновлює стару лексему  -  
      // присвоєння не відбувається
      strcpy(token, temp_token);
      tok_type = ttok_type;
    } else {
      get_token(); // вилучаємо наступну частину виразу exp
      eval_exp2(result);
      vars[slot] = result;
      return;
    }
  }
  eval_exp2(result);
}

Очевидно, що ця функція наперед переглядає вираз, щоб визначити, чи дійсно треба виконувати присвоювання. Це необхідно робити тому, що ім'я змінної завжди передує оператору присвоювання, але само по собі не гарантує, що за ним обов’язково буде слідувати оператор присвоювання. Інакше кажучи, аналізатор розпізнає вираз А = 100 як операцію присвоювання і може відрізнити його від виразу А/10/.Для цього функція eval_exp1() зчитує з вхідного потоку наступну лексему. Якщо вона нетримає знак рівності, лексема повертається у вхідний потік з допомогою функції putback(), яка являється частиною класу parser.

//повертає лексему у вхідний потік
void parser::putback() {
  char *t;
  t = token;
  for(; *t; t++) 
    exp_ptr--;
}

Після зроблених змін, клас parser приймає наступний вигляд.

/* Програма, яка виконує рекурсивний спуск виразів зі змінними */
 
#include <iostream>
#include <cstdlib>
#include <cctype>
#include <cstring>
using namespace std;
enum types { DELIMITER = 1, VARIABLE, NUMBER};
const int NUMVARS = 26;
class parser {
  char *exp_ptr; // вказує на вираз
  char token[80]; // зберігає поточну лексему
  char tok_type; // зберігає тип лексеми
  double vars[NUMVARS]; // зберігає значення змінних
  void eval_exp1(double &result);
  void eval_exp2(double &result);
  void eval_exp3(double &result);
  void eval_exp4(double &result);
  void eval_exp5(double &result);
  void eval_exp6(double &result);
  void atom(double &result);
  void get_token();
  void putback();
  void serror(int error);
  double find_var(char *s);
  int isdelim(char c);
public:
  parser();
  double eval_exp(char *exp);
};
 
// parser конструктор
parser::parser() {
  int i;
  exp_ptr = NULL;
  for(i=0; i<NUMVARS; i++)
  vars[i] = 0.0;
}
 
// Початкова точка аналізатора
double parser::eval_exp(char *exp) {
  double result;
  exp_ptr = exp;
  get_token();
  if (!*token) {
    serror(2); // вираз пустий
    return 0.0;
  }
  eval_exp1(result);
  if (*token) serror(0); // остання лексема повинна бути 0-символом
    return result;
}
 
// присвоювання
void parser::eval_exp1(double &result) {
  int slot;
  char ttok_type;
  char temp_token[80];
  if(tok_type==VARIABLE) {
  // зберігає стару лексему
    strcpy(temp_token, token);
    ttok_type = tok_type;
    // знаходимо індекс змінної
    slot = toupper(*token) - 'A';
    get_token();
    if (*token != '=') {
      putback(); // повертає поточну лексему 
      // відновлює стару – присвоювання не відбувається
      strcpy(token, temp_token);
      tok_type = ttok_type;
    } else {
      get_token(); //вилучаємо наступну частину виразу exp
      eval_exp2(result);
      vars[slot] = result;
      return;
    }
  }
  eval_exp2(result);
}
 
// додаємо або віднімаємо два терма 
void parser::eval_exp2(double &result) {
  register char op;
  double temp;
  eval_exp3(result);
  while((op = *token) == '+' || op == '-') {
    get_token();
    eval_exp3(temp);
    switch (op) {
    case '-':
      result = result - temp;
      break;
    case '+':
      result = result + temp;
      break;
    }
  }
}
 
// множимо або ділимо два фактори
void parser::eval_exp3(double &result) {
  register char op;
  double temp;
  eval_exp4(result);
  while ((op = *token) == '*' || op == '/' || op == '%') {
    get_token();
    eval_exp4(temp);
    switch (op) {
    case '*':
      result = result * temp;
      break;
    case '/':
      result = result / temp;
      break;
    case '%':
      result = (int) result % (int) temp;
      break;
    }
  }
}
 
// піднесення до степеня
void parser::eval_exp4(double &result) {
  double temp, ex;
  register int t;
  eval_exp5(result);
  if (*token== '^') {
    get_token();
    eval_exp4(temp);
    ex = result;
    if (temp==0.0) {
      result = 1.0;
      return;
    }
    for(t=(int)temp-1; t>0; --t) result = result * (double)ex;
  }
}
 
//Виконання унарних операцій + чи -.
void parser::eval_exp5(double &result) {
  register char op;
  op = 0;
  if ((tok_type == DELIMITER) && *token=='+' || *token == '-') {
    op = *token;
    get_token();
  }
  eval_exp6(result);
  if (op=='-')
    result = -result;
}
 
// аналіз виразу, який містить дужки
void parser::eval_exp6(double &result) {
  if ((*token == '(')) {
    get_token();
    eval_exp2(result);
    if (*token != ')')
      serror(1);
    get_token();
  } else
    atom(result);
}
 
// вилучає число або значення змінної
void parser::atom(double &result) {
  switch(tok_type) {
  case VARIABLE:
    result = find_var(token);
    get_token();
    return;
  case NUMBER:
    result = atof(token);
    get_token();
    return;
  default:
    serror(0);
  }
}
 
// повертає лексему у вхідний потік
void parser::putback() {
  char *t;
  t = token;
  for(; *t; t++) exp_ptr--;
}
 
// Виводить на екран повідомлення про помилку
void parser::serror(int error) {
  static char *e[]= {
  "Syntax Error",
  "Unbalanced Parentheses",
  "No expression Present"
  };
  cout << e[error] << endl;
}
 
// отримує наступну лексему.
void parser::get_token() {
  register char *temp;
  tok_type = 0;
  temp = token;
  *temp = '\0';
  if (!*exp_ptr)
    return; // в кінці виразу
  while(isspace(*exp_ptr))
    ++exp_ptr; // пропуск роздільника
  if (strchr("+-*/%^=()", *exp_ptr)) {
    tok_type = DELIMITER;
    // перехід до наступного символу
    *temp++ = *exp_ptr++;
  } else if (isalpha(*exp_ptr)) {
    while(!isdelim(*exp_ptr)) 
    *temp++ = *exp_ptr++;
    tok_type = VARIABLE;
  } else if(isdigit(*exp_ptr)) {
    while (!isdelim(*exp_ptr)) 
    *temp++ = *exp_ptr++;
    tok_type = NUMBER;
  }
  *temp = '\0';
}
 
// Якщо с – роздільник, то повертає true
int parser::isdelim (char c) {
  if (strchr(" +-/*%^=()", c) || c==9 || c=='\r' || c==0)
    return 1;
  return 0;
}
 
// повертає значення змінної
double parser::find_var(char *s) {
  if(!isalpha(*s)) {
    serror(1);
    return 0.0;
  }
  return vars[toupper(*token)-'A'];
}

Для перевірки нової версії можна знову застосувати функцію main(), яка така ж як попередня.

// тестування
int main() {
  char expstr[80];
 
  cout << " Для закінчення введіть крапку.\n";
 
  parser ob; // створення аналізатора
 
  for (;;) {
    cout << " Введіть вираз: ";
    cin.getline(expstr, 79);
    if (*expstr=='.') break;
    cout << " Відповідь: " << ob.eval_exp(expstr) << "\n\n";
  };
  return 0;
}

Тепер можна обчислити складніші вирази, наприклад:

X = 10/4
X – 12
X = (X * (X – 21)^2-12)/2