Разборщик арифметических выражений

Разборщик арифметических выражений

Отчет о лабораторной работе

Введение

Одной из главных причин, лежащих в основе появления языков пpогpаммиpования высокого уpовня, явились вычислительные задачи, тpебующие больших объёмов pутинных вычислений. Поэтому к языкам пpогpаммиpования пpедъявлялись тpебования максимального пpиближения фоpмы записи вычислений к естественному языку математики. В этой связи одной из пеpвых областей системного пpогpаммиpования сфоpмиpовалось исследование способов анализа выpажений.

Формальной грамматикой называется способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Естественным образом возникает такой термин как синтакси́ческий ана́лиз (па́рсинг) — это процесс сопоставления линейной последовательности лексем (слов) языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Синтаксический анализатор (парсер) — это программа или часть программы, выполняющая синтаксический анализ.

При парсинге исходный текст преобразуется в структуру данных, обычно — в дерево, которое отражает синтаксическую структуру входной последовательности и хорошо подходит для дальнейшей обработки.

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

В данной области были получены многочисленные pезультаты, однако наибольшее pаспpостpанение получил метод парсинга с помощью обpатной польской записи, котоpую пpедложил польский математик Я. Лукашевич.

Синтакическому анализу и вычислению значения арифметического выражения с помощью метода обратной польской записи посвящена данная лабораторная работа.

Задачи

·  Рассмотреть метод обратной польской записи – алгоритм разбора арифметического выражения

·  Реализовать рассматриваемый алгоритм на языке программирования высокого уровня С++, используя объектно-ориентированную модель

·  В ходе реализации использовать структуру – стек

·  Реализовать возможность пользовательского ввода арифметического выражения с параметрами, а также вывода численного значения данного выражения

Обратная польская запись

Обра́тная по́льская нота́ция (ОПН) (RPN, англ. Reverse Polish Notation) — форма записи математических выражений, в которой операнды расположены перед знаками операций. Также именуется как обратная польская запись, обратная бесскобочная запись (ОБЗ), постфиксная нотация, бесскобочная символика Лукашевича, польская инверсная запись, ПОЛИЗ.

Стековой машиной называется алгоритм, проводящий вычисления по обратной польской записи

Обратная польская нотация была разработана австралийским философом и специалистом в области теории вычислительных машин Чарльзом Хэмблином в середине 1950-х на основе польской нотации, которая была предложена в 1920 году польским математиком Яном Лукасевичем. Работа Хэмблина была представлена на конференции в июне 1957, и издана в 1957 и 1962.

Отличительной особенностью обратной польской нотации является то, что все аргументы (или операнды) расположены перед знаком операции. В общем виде запись выглядит следующим образом:

·  Запись набора операций состоит из последовательности операндов и знаков операций. Операнды в выражении при письменной записи разделяются пробелами.

·  Выражение читается слева направо. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность её операндов и её знак, после чего выражение вычисляется дальше по тому же правилу.

·  Результатом вычисления выражения становится результат последней вычисленной операции.

Вычисления на стеке

Автоматизация вычисления выражений в обратной польской нотации основана на использовании стека. Алгоритм вычисления для стековой машины элементарен:

1.  Обработка входного символа

o  Если на вход подан операнд, он помещается на вершину стека.

o  Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.

2.  Если входной набор символов обработан не полностью, перейти к шагу 1.

3.  Когда выражение прочитано полностью, все оставшиеся в стеке операторы выталкиваются в выходную строку. После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.

Реализация стековой машины, как программная, так и аппаратная, чрезвычайно проста и может быть очень эффективной. Обратная польская запись совершенно унифицирована — она принципиально одинаково записывает унарные, бинарные, тернарные и любые другие операции, а также обращения к функциям, что позволяет не усложнять конструкцию вычислительных устройств при расширении набора поддерживаемых операций. Это и послужило причиной использования обратной польской записи в некоторых научных и программируемых микрокалькуляторах.

Пример вычисления выражений

Выражение (1 + 2) × 4 + 3 в ОПН может быть записано так: 1 2 + 4 × 3 +

Вычисление производится следующим образом (указано состояние стека после выполнения операции):

Результат, 15, в конце вычислений находится на вершине стека.

Руководство пользователя

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

Рис. 1. Окно программы

1.  Окно для пользовательского ввода арифметического выражения;

2.  Окно численного значения выражения;

3.  Кнопка построения таблицы параметров выражения;

4.  Кнопка вычисления значения выражения;

5.  Таблица значений параметров выражения;

6.  Поле вывода ошибок в случае введения некорректных данных.

Для получения результата необходимо:

1.  Ввести арифметическое выражение в окно (1);

2.  Нажать кнопку (3), после чего станет доступна для ввода значений таблица параметров (5), в случае наличия таковых;

3.  Заполнить таблицу (5) пользовательскими значениями;

4.  Нажать кнопку (4), после чего в окне (2) отобразится значение введенного выражения, либо в поле (6) сообщение об ошибке в случае некорректности выражения или введенных параметров;

5.  В случае ошибки необходимо повторить описанную процедуру с начала.

Руководство программиста

Рассмотрим программную реализацию поставленной задачи. Дадим краткое описание методов разработанных классов.

Для написания программного приложения использовался язык программирования высокого уровня C++ со средой разработки Visual Studio 2008. Для создания пользовательского интерфейса использовалась библиотека Windows Forms, являющаяся частью Microsoft. NET Framework.

Для реализации поставленных задач были разработаны следующие классы:

1.  CStack – динамическая структура стек;

2.  CExpression – арифметическое выражение и операции над ним.

Шаблонный класс CStack

Данный класс предназначен для реализации стека — структура данных, в которой доступ к элементам организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю. Данная реализация позволяет производить динамическое расширение стека в случае его переполнения.

В таблице 1 приведено описание некоторых методов класса Stack.

Табл. 1. Методы класса CStack

Класс CExpression

Данный класс предназначен для хранения и обработки пользовательского арифметического выражения. В таблице 2 приведено описание некоторых методов класса CExpression.

Табл. 2. Методы класса CExpression

В реализации класса используется структура типа FunctionDescriptor – дескриптор функции, содержащий в себе символьное имя функции, признак бинарости и указатель на реализацию функции, ассоциативный массив которых DescriptorsTable дает возможность добавления в программу новых пользовательских функций(унарных и бинарных).

Данная реализация позволяет производить расчет выражения при известных значениях параметра за один проход по выражению без непосредственного составления обратной польской записи данного с использованием стековой машины.

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

Выводы

1.  Рассмотрена обратная польская запись выражения и машина стеков – алгоритм вычисления значения выражения, основанный на данной нотации;

2.  Написана программа на языке высокого уровня C++, удовлетворяющая поставленным задачам с требуемыми входными и выходными данными, а также пользовательским интерфейсом;

3.  В ходе реализации реализована структура стека в виде соответствующего класса.

Приложение

Реализация класса CExpression

// CExpression.cpp

// Арифметическое выражение

#include "stdafx. h"

#include "Expression. h"

#include "Functions. h"

// Принадлежность элемента к цифрам

#define IS_DIGIT(ch) ((ch >= ‘0’ && ch <= ‘9’))

// Принадлежность элемента к символам латиницы

#define IS_CHARACTER(ch) ((ch >= ‘a’&& ch <= ‘z’) || (ch >= ‘A’ && ch <= ‘Z’))

// Приоритет с учетом вложенности скобок

#define PRIORITY(nestingLevell, nPriority) (nestingLevell << 3 | nPriority)

bool CExpression::bIsInitialized = false;

map<string, FunctionDescriptor> CExpression::_funcDescriptors;

// Конструктор

CExpression::CExpression(const string& inputString) : _operandStack(), _functionStack()

{

_strExpression = "(" + inputString + ")";

_value = NULL;

_arrVariable. clear();

//_nameVariable = new string[inputString. length()];

_bCorrect = true;

if (!bIsInitialized)

{

bIsInitialized = true;

// Дескриптор функций

CExpression::RegisterFunction("+", 0, Plus);

CExpression::RegisterFunction("-", 0, Minus);

CExpression::RegisterFunction("*", 1, Mult);

CExpression::RegisterFunction("/", 1, Div);

CExpression::RegisterFunction("^", 2, pow);

CExpression::RegisterFunction("sin", 3, sin);

CExpression::RegisterFunction("cos", 3, cos);

CExpression::RegisterFunction("tan", 3, tan);

CExpression::RegisterFunction("log", 3, log);

}

_BuildVariableArray(_strExpression);

}

// Получить выражение в обратной польской нотации

string CExpression::GetRPN(void)

{

return _rpnString;

}

// Получить корректность выражения

bool CExpression::IsCorrect(void)

{

return _bCorrect;

}

// Получить строковое представление выражения

string CExpression::GetStrExpression(void)

{

return this->_strExpression;

}

// Получить массив переменных

ArrayVariable CExpression::GetArrayVariable(void)

{

return _arrVariable;

}

// Устанвить значение в массив переменных

void CExpression::AddVariableValue(string variableName, double variableValue)

{

_arrVariable[variableName] = variableValue;

}

// Построение массива переменных

void CExpression::_BuildVariableArray(const string& strExpression)

{

int nNestingLevel = 0; // Счетчик уровня вложенности скобок

const char* pCurrentExpression = strExpression. c_str();

do

{

char* pNextEspression;

ExpressionElement exprElement = _ReadNextExpression(pCurrentExpression, &pNextEspression);

switch (exprElement. elType)

{

case BRACKET: // Скобки

if (exprElement. bLeftBracket)

{

nNestingLevel++;

}

else

{

nNestingLevel—;

}

break;

case VARIABLE: // Выражение

AddVariableValue(exprElement. strName, 0);

break;

}

pCurrentExpression = pNextEspression;

}

while (nNestingLevel && IsCorrect());

}

// Добавить строку к польской записи

void CExpression::_AddUnitToRPN(string strName)

{

_rpnString += strName;

}

// Выделение логических элементов строки

ExpressionElement CExpression::_ReadNextExpression(const char* expression, char** nextExpression) const

{

ExpressionElement exprElement; // Результат — структура

while (*expression++ == ‘ ‘); // Игнорируем пробелы

expression—;

// Признак базовой операции

bool bBasicOperation =

*expression == ‘+’ ||

*expression == ‘-‘ ||

*expression == ‘/’ ||

*expression == ‘*’ ||

*expression == ‘^’;

string strExpr;

if (bBasicOperation || IS_CHARACTER(*expression)) // Базовая операция или символ — подозрение на функцию или переменную

{

// Cчитываем первый символ

strExpr += *expression++;

if (!bBasicOperation) // Не базовая операция

{

while (IS_CHARACTER(*expression) || IS_DIGIT(*expression)) // Читаем допустимые символы ([a..z] [A..Z] [0..9])

{

strExpr += *expression++;

}

}

// Ищем в списке функций функцию с именем strExpr

DescriptorsTable::const_iterator it = _funcDescriptors. find(strExpr);

if (it!= _funcDescriptors. end())

{

//Найдена, тогда копируем ее описание

exprElement. elType = FUNCTION;

exprElement. strName = strExpr;

exprElement. funcDescriptor = it->second;

}

else

{

// Является переменной

exprElement. elType = VARIABLE;

exprElement. nPriority = 4;

exprElement. strName = strExpr;

}

// Возвращаем указатель на следующий разбираемый символ

*nextExpression = (char*)expression;

}

// Символ является цифрой

else if (IS_DIGIT(*expression))

{

exprElement. strName = strExpr;

exprElement. elType = CONSTANT;

exprElement. nPriority = 4;

// Считываем символы-цифры пока не получим полное число

exprElement. dblValue = strtod(expression, nextExpression);

}

else if (*expression == ‘(‘)

{

exprElement. elType = BRACKET;

exprElement. bLeftBracket = true;

*nextExpression = (char*)(expression + 1);

}

else if (*expression == ‘)’)

{

exprElement. elType = BRACKET;

exprElement. bLeftBracket = false;

*nextExpression = (char*)(expression + 1);

}

else

{

// Встречается недопустимый символ — ошибка!

exprElement. elType = ERROR;

}

// Возвращаем функцию, переменную, операцию или число

return exprElement;

}

// Разборщик выражения

void CExpression::Parse(const string& strExpression)

{

// Нулевая константа

ExpressionElement CONST_NULL;

CONST_NULL. elType = CONSTANT;

CONST_NULL. strName = "0";

CONST_NULL. dblValue = 0;

int nNestingLevel = 0; // Счетчик уровня вложенности скобок

bool bBracket = false; // Признак открывающей скобки

const char* pCurrentExpression = strExpression. c_str();

ExpressionElement currentFunction; // Текущая функция

do

{

char* pNextEspression;

ExpressionElement exprElement = _ReadNextExpression(pCurrentExpression, &pNextEspression);

switch (exprElement. elType) // Производим выборку по типу логического блока строки

{

case BRACKET: // Скобки

if (exprElement. bLeftBracket)

{

nNestingLevel++;

bBracket = true; // Признак открытой скобки

}

else

{

nNestingLevel—;

bBracket = false;

}

break;

case CONSTANT: // Константа

_operandStack. Push(exprElement);

bBracket = false;

break;

case VARIABLE: // Выражение

exprElement. dblValue = this->_arrVariable[exprElement. strName];

_operandStack. Push(exprElement);

bBracket = false;

break;

case FUNCTION: // Функция

{

// Унарный минус перед скобкой или в начале выражения

if (exprElement. funcDescriptor. strSymbol == "-" && bBracket)

{

_operandStack. Push(CONST_NULL);

}

bBracket = false; // Сброс признака открытой скобки

// Определяем абсолютный приоритет функции в выражении

exprElement. funcDescriptor. nPriority = PRIORITY(nNestingLevel, exprElement. funcDescriptor. nPriority);

// Стек функции пуст или приоритет вершинного элемента <= приоритета текущей функции

if (_functionStack. IsEmpty() || exprElement. funcDescriptor. nPriority > _functionStack. Peek().funcDescriptor. nPriority)

{

_functionStack. Push(exprElement);

}

else

{

// Вытесняем функции из стека и производим вычисление их значений

while (!_functionStack. IsEmpty() && exprElement. funcDescriptor. nPriority <= _functionStack. Peek().funcDescriptor. nPriority)

{

СalculateValueFunction(_functionStack. Pop());

}

_functionStack. Push(exprElement);

}

break;

}

case ERROR: // Ошибка

_bCorrect = false;

}

pCurrentExpression = pNextEspression;

}

while (nNestingLevel && IsCorrect());

// Вытесняем оставшиеся функции из стека и производим вычисление их значений

while (!_functionStack. IsEmpty() && IsCorrect())

{

СalculateValueFunction(_functionStack. Pop());

}

if (!_operandStack. IsEmpty())

{

_value = _operandStack. Pop().dblValue;

}

else

_bCorrect = false;

// Стек операндов не пуст — выражение не корректно

if (!_operandStack. IsEmpty())

_bCorrect = false;

}

// Вычислить значение функции

ExpressionElement CExpression::СalculateValueFunction(const ExpressionElement& currentFunction)

{

ExpressionElement res = { CONSTANT };

res. dblValue = 0;

if (!_operandStack. IsEmpty())

{

ExpressionElement x1 = _operandStack. Pop();

if (!currentFunction. funcDescriptor. bBinary)

{

res. dblValue = currentFunction. funcDescriptor. pfcUnary(x1.dblValue);

}

else if (currentFunction. funcDescriptor. bBinary && !_operandStack. IsEmpty())

{

ExpressionElement x2 = _operandStack. Pop();

res. dblValue = currentFunction. funcDescriptor. pfcBinary(x2.dblValue, x1.dblValue);

}

else

{

_bCorrect = false;

}

_operandStack. Push(res);

}

else

{

_bCorrect = false;

}

return res;

}

// Зарегистрировать функцию

bool CExpression::RegisterFunction(const string& strName, const FunctionDescriptor& funcDescriptor)

{

// Признак наличия функции

bool bRet = _funcDescriptors. find(strName) == _funcDescriptors. end();

if (bRet)

{

// Регистрируем функцию

_funcDescriptors[strName] = funcDescriptor;

}

return bRet;

}

// Зарегистрировать функцию(унарную)

bool CExpression::RegisterFunction(const string& strName, int nPriority, UnaryFunction pFunction)

{

FunctionDescriptor funcDescriptor;

funcDescriptor. strSymbol = strName;

funcDescriptor. bBinary = false;

funcDescriptor. nPriority = nPriority;

funcDescriptor. pfcUnary = pFunction;

return RegisterFunction(strName, funcDescriptor);

}

// Зарегистрировать функцию(бинарную)

bool CExpression::RegisterFunction(const string& strName, int nPriority, BinaryFunction pFunction)

{

FunctionDescriptor funcDescriptor;

funcDescriptor. strSymbol = strName;

funcDescriptor. bBinary = true;

funcDescriptor. nPriority = nPriority;

funcDescriptor. pfcBinary = pFunction;

return RegisterFunction(strName, funcDescriptor);

}

// Получить значение

double CExpression::GetValue(void)

{

return _value;

}

Список литературы

1.  А. В. Ахо, Р. Сети, Д. Д. Ульман. Компиляторы: принципы, технологии и инструменты. М.: «Вильямс», 2003. С. 51.

2.  http://ru. wikipedia. org

3.  http://algolist. manual. ru