Перейти до вмісту

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

Додати посилання
завершено на 75%
Матеріал з Вікіпідручника

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

Вступ

[ред.]

Незважаючи на те, що стандарт мови C++ досить обширний, деякі теми, такі як синтаксичний аналіз виразів в ньому не розглядаються. Програми синтаксичного аналізу використовуються для обчислення значень алгебраїчних виразів, наприклад (100-23)*213. Сьогодні синтаксичні аналізатори оточені певною загадковістю. З різних причин, процедури що використовуються в процесі синтаксичного аналізу відомі небагатьом. Навіть дуже розумні програмісти іноді пасують перед необхідністю синтаксичного аналізу.

Насправді синтаксичний аналіз виразів - досить проста процедура. Ця простота є наслідком строгих правил алгебри. В цій роботі ми оглянемо програму аналізу методом рекурсивного спуску (recursive-descent parser) та всі її процедури. Однак перш ніж приступити до розробки, варто трохи розповісти про вирази і правила їх граматичного поділу.

Вирази

[ред.]

Оскільки програма синтаксичного поділу обчислює арифметичні вирази, необхідно ясно уявити перед собою, з яких частин складається вираз. Розглянемо вирази з наступних компонентів:

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

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

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

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

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

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

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

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

[ред.]

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

<вираз> ::= <доданок> [+ <доданок>] [- <доданок>]
<доданок> ::= <атом> [* <атом>] [/ <атом>]
<атом> ::= <змінна> | <число> | (<вираз>)

Квадратні дужки містять необов'язковий елемент, а символ ::= інтерпритується як "породжує". Правила, вказані вище, часто називають породжуючими правилами, або продукціями. Тому, визначення доданка можна було б озвучити так: "Доданок породжує атом чи атом помножений чи поділений на атом". Зверніть увагу на те, що породжуючі правила неявно враховують пріоритет операцій.

Вираз: 

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.

Потрібно знати дві речі:

  1. Породжені правила неявно враховують приорітет операторів.
  2. Цей метод аналізу і обчислення виразу дуже схожий на спосіб, з допомогою якого люди самі обчислюють математичні вирази.

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

Клас 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-рядках. Інші два поля, token і tok_type, використовуються в лексичному аналізі, про що буде говоритись пізніше.

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

Функція serror() призначена для обробки синтаксичних помилок, створених у виразі. Функції get_token() і isdelim() використовуються для розбиття виразу на складові частини.

Лексичний аналіз

[ред.]

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

Кожен компонент виразу називається лексемою (токеном). Наприклад, вираз 

A * B - (W + 10)

містить лексеми А, *, B, -, (, W +, 10, і ). Кожна лексема представляє собою нерозділювану частину виразу.

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

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

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

// Отримує наступну лексему.
void parser::get_token() {
  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;
}

Придивимось до цих функцій. Після перших ініціалізацій функція get_token() перевіряє, чи не знайдено кінець вхідного рядка. Для цього вона перевіряє символ, на який вказує вказівник exp_ptr. Якщо його значення рівне нулю, то досягнуто кінця виразу. Якщо у виразі залишились ще не вилучені лексеми, функція get_token() ігнорує всі пропуски що йдуть на початку. Оскільки пропуски ігноруються, вказівник exp_ptr може вказувати або на число, змінну, оператор або кінець виразу. Якщо наступним символом є оператор, він записується в змінну token, а в змінну tok_type записується константа DELIMITER. Якщо наступний символ - буква, то припускається, що лексема є змінною, а змінна 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
\0 0

Проста програма синтаксичного аналізу виразів

[ред.]

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

#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
Отримано з https://uk.wikibooks.org/w/index.php?title=Реалізація_алгоритму_рекурсивного_спуску_з_прикладами_на_C%2B%2B&oldid=37346