Срок выполнения задания:
до 3 апреля
Написать реализацию алгоритмов перевода арифметического выражения из инфиксной формы в постфиксную и вычисления выражения, записанного в постфиксной форме.
В теме Стек на массиве приводится описание алгоритмов перевода арифметического выражения, заданного в виде строки из инфиксной формы в префиксную, то есть например:
(2+2)*(3-1) преобразуется в 2 2 + 3 1 - *
Предполагается:
- входная строка содержит правильно построенное выражение
- числа положительные, целые, могут состоять из нескольких цифр
- все действия производятся над целыми, результат - целый
Для перевода из одной формы в другую мы используем стек, построенный на основе шаблона. Этот стек должен быть описан в файле include/tstack.h.
Для использования стека достаточно его инстанцировать с указанием типа данных:
TStack<char, 100> stack1;
TStack<int, 100> stack2;Функции должны иметь следующую сигнатуру и располагаться в файле src/alg.cpp:
// преобразование выражение в постфиксную форму
std::string infx2pstfx(std::string inf) {
}
// вычисление выражения, записанного в постфиксной форме
int eval(std::string post) {
}
Описания параметров функций:
- inf - строка, содержащая запись арифметического выражения в инфиксной форме, например "(2+2)*2"
- post - строка, содержащая запись арифметического выражения в постфиксной форме, например "2 2 + 2 *"
В этом задании в качестве строк используется тип std::string из стандартной библиотеки С++
Описания функций:
-
Функция infx2pstfx должна преобразовывать входную строку, содержащую выражение в инфиксной форме в выходную строку, которая содержит то же выражение в постфиксной фоме. Для отделения операндов друг от друга нужно использовать пробелы.
-
Функция eval должна вычислять выражение, записанное в постфиксном виде и выдавать целое значение. Все расчеты ведутся в целых числах!
Помимо указанных функций, в файл alg.cpp можно помещать определения вспомогательных функций.