Вычисление математических выражений

06/06/2017 by Валентина Андриеш

Условие задачи:
Пусть дана строка, которая является математическим выражением, содержащим числа, переменные и различные операции. Требуется вычислить его значение.

Помимо создания прототипа работы элементарного калькулятора, рассмотрим решение одной из подзадач — «Многочлен», найденную на просторах сайта e-olymp.

Входные данные:

В первой строке входного файла записано математическое выражение. Между операндами используются бинарные операторы ([latex]+[/latex], [latex]–[/latex], [latex]\ast[/latex], [latex]/[/latex], [latex]\wedge[/latex]) и унарный знак ([latex]–[/latex]). Если данное выражение представляет собой многочлен, то каждый одночлен записывается как [Коэффициент*]x[^Степень] или [Коэффициент], где [Коэффициент] — натуральное число, не превосходящее 100, x — символ переменной (всегда маленькая латинская буква [latex]x[/latex]), [Степень] — натуральное число, не превосходящее 4. Параметры, взятые в квадратные скобки, могут быть опущены. Во второй строке будет записано одно целое число — значение x. Все числа в исходном файле по модулю не превосходят 100. Количество одночленов не более 10 (могут быть одночлены одинаковой степени).

Выходные данные:

В выходной файл нужно записать одно число — результат вычисления данного математического выражения.

Тесты:

Входные данные		Выходные данные
16-(4^3+52/2)		-74
-2+x^1-3x^2+x^2+100x^3-2*x	-7	-34393
-2x^2+16x^3-x	(-3)^4	8489853
x^2-5x+15-8x^4	0	15

Код на с++:

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

 //в этой функции рассмотрим все возможные операции, что могут встретиться в строке
bool operation(char c){
    return c=='+' || c=='-' || c=='*' ||  c=='/' || c=='^';
}

//данная функция будет возвращать приоритет поступившей операции
int prioritet(char op){ 
    if(op<0) return 3;
    else{
        if(op == '+' || op == '-')return 1;
        else if(op == '*' || op == '/' )return 2;
        else if(op == '^')return 4;
        else return -1;
    }
}

//следующая функция описывает принцип работы каждого оператора
void action(vector<long> &value, char op){
    if(op<0){                            //для унарных операций
        long unitar=value.back();
        value.pop_back();
        if(-op=='-')value.push_back(-unitar);
    }
    else{                               //для бинарных операций
        long right = value.back();
        value.pop_back();
        long left = value.back();
        value.pop_back();
        if(op=='+')value.push_back(left+right);
        else if(op=='-')value.push_back(left-right);
        else if(op=='*')value.push_back(left*right);
        else if(op=='/')value.push_back(left/right);
        else if(op=='^')value.push_back(pow(left,right));
    }
}

long calculus(string &formula){
    bool unary=true;        //создадим булевскую переменную, для распределения операторов на унарные и бинарные
    vector<long>value;        //заведем массив для целых чисел
    vector<char>op;           //и соответственно для самых операторов
    for(int i=0; i<formula.size(); i++){
            if(formula[i]=='('){    //если текущий элемент — открывающая скобка, то положим её в стек
                op.push_back('(');  
                unary=true;
            }
            else if(formula[i]==')'){
                while(op.back()!='('){  //если закрывающая скобка - выполняем все операции, находящиеся внутри этой скобки
                    action(value, op.back());
                    op.pop_back();
                }
                op.pop_back();
                unary=false;
            }
            else if(operation(formula[i])){ //если данный элемент строки является одни из выше перечисленных операндов,то
                char zn=formula[i];
                if(unary==true)zn=-zn; //придает отрицательное значение, для распознавания функции унарности оператора 
                while(!op.empty() && prioritet(op.back())>=prioritet(zn)){
                    action(value, op.back());   //выполняем сами алгебраические вычисления, где все уже операции упорядочены  
                    op.pop_back();              //в одном из стеков по строгому убыванию приоритета, если двигаться от вершины
                }
                op.push_back(zn);
                unary=true;
            }
            else{
                string number;      //заведем строку для найденных числовых операндов
                while(i<formula.size() && isdigit(formula[i]))number+=formula[i++];//распознаем их с помощью библиотечной функции строк
                i--;
                value.push_back(atol(number.c_str()));//поместим в наш стек с числовыми выражениями
                unary=false;
            }
        }
    while(!op.empty()){     //выполним еще не использованные операции в стеке 
        action(value, op.back());
        op.pop_back();
    }
    return value.back(); //получим на выходе значение выражения
}
    
int main() {
    string formula,x; //введем две строки: сам многочлен/числовое выражение и по необходимости значение переменной 
    cin>>formula>>x;
    if(x[0]=='-'){  //для слаженной работы унитарного минуса при отрицательном значении переменной, заключим его в скобки
        x.insert(x.begin(),'(');
        x.insert(x.end(),')');
    }
    int size=2*formula.size();  //зададим максимальный размер строки с учетом замены переменной
    for(int i=0; i<size; i++){
        if(formula[i]=='x'){
            formula.erase(i,1);
            formula.insert(i,x);//проведем замену
        }
    }
    cout<<calculus(formula);  //выведем ответ
    return 0;
}

100

101

#include <iostream>

#include <vector>

#include <string>

#include <cmath>

using namespace std;

//в этой функции рассмотрим все возможные операции, что могут встретиться в строке

bool operation(char c){

return c=='+' || c=='-' || c=='*' || c=='/' || c=='^';

}

//данная функция будет возвращать приоритет поступившей операции

int prioritet(char op){

if(op<0) return 3;

else{

if(op == '+' || op == '-')return 1;

else if(op == '*' || op == '/' )return 2;

else if(op == '^')return 4;

else return -1;

}

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

void action(vector<long> &value, char op){

if(op<0){ //для унарных операций

long unitar=value.back();

value.pop_back();

if(-op=='-')value.push_back(-unitar);

}

else{ //для бинарных операций

long right = value.back();

value.pop_back();

long left = value.back();

value.pop_back();

if(op=='+')value.push_back(left+right);

else if(op=='-')value.push_back(left-right);

else if(op=='*')value.push_back(left*right);

else if(op=='/')value.push_back(left/right);

else if(op=='^')value.push_back(pow(left,right));

}

long calculus(string &formula){

bool unary=true; //создадим булевскую переменную, для распределения операторов на унарные и бинарные

vector<long>value; //заведем массив для целых чисел

vector<char>op; //и соответственно для самых операторов

for(int i=0; i<formula.size(); i++){

if(formula[i]=='('){ //если текущий элемент — открывающая скобка, то положим её в стек

op.push_back('(');

unary=true;

}

else if(formula[i]==')'){

while(op.back()!='('){ //если закрывающая скобка - выполняем все операции, находящиеся внутри этой скобки

action(value, op.back());

op.pop_back();

}

op.pop_back();

unary=false;

}

else if(operation(formula[i])){ //если данный элемент строки является одни из выше перечисленных операндов,то

char zn=formula[i];

if(unary==true)zn=-zn; //придает отрицательное значение, для распознавания функции унарности оператора

while(!op.empty() && prioritet(op.back())>=prioritet(zn)){

action(value, op.back()); //выполняем сами алгебраические вычисления, где все уже операции упорядочены

op.pop_back(); //в одном из стеков по строгому убыванию приоритета, если двигаться от вершины

}

op.push_back(zn);

unary=true;

}

else{

string number; //заведем строку для найденных числовых операндов

while(i<formula.size() && isdigit(formula[i]))number+=formula[i++];//распознаем их с помощью библиотечной функции строк

i--;

value.push_back(atol(number.c_str()));//поместим в наш стек с числовыми выражениями

unary=false;

}

while(!op.empty()){ //выполним еще не использованные операции в стеке

action(value, op.back());

op.pop_back();

}

return value.back(); //получим на выходе значение выражения

}

int main() {

string formula,x; //введем две строки: сам многочлен/числовое выражение и по необходимости значение переменной

cin>>formula>>x;

if(x[0]=='-'){ //для слаженной работы унитарного минуса при отрицательном значении переменной, заключим его в скобки

x.insert(x.begin(),'(');

x.insert(x.end(),')');

}

int size=2*formula.size(); //зададим максимальный размер строки с учетом замены переменной

for(int i=0; i<size; i++){

if(formula[i]=='x'){

formula.erase(i,1);

formula.insert(i,x);//проведем замену

}

cout<<calculus(formula); //выведем ответ

return 0;

}

Описание решения задачи:

В основе решения данной задачи лежит алгоритм, который переводит математические выражения в обратную польскую нотацию, что в дальнейшем позволяет решать данные выражения. Особенностью данной записи, в отличие от привычных нам, является постфиксная форма представления, где операторы математической формулы размещены после своих операндов.
Рассмотрим само решение. На входе программа получает две строки: одна из них представляет само математическое выражение/многочлен — [latex]formula[/latex] и при необходимости вторую — [latex]x[/latex], где передается значение переменной, использованной в многочлене. Если же на вход поступил не многочлен, данная строка сразу же идет на преобразование из инфиксной формы(оператор размещен между операндами) в постфиксную. В ином случае, с помощью встроенных библиотечных функций класса [latex]string[/latex] мы заменяем все переменные на вторую строку [latex]x[/latex] и выполняем точно такую же работу. Разберем ближе сам алгоритм преобразования строки и ее подсчета. Заведём два стека: [latex]value[/latex] — для чисел, [latex]op[/latex] — операций и скобок. Для второго стека является основным предусловие, что все операции упорядочены в нём по строгому убыванию приоритета, если двигаться от вершины стека. Будем идти слева направо по выражению в обратной польской нотации; если текущий элемент — число, то кладём на вершину стека [latex]value[/latex] его значение; если же текущий элемент — операция, то достаём из стека два верхних элемента (или один, если операция унарная), применяем к ним операцию, и результат кладём обратно в стек. Итого в [latex]value[/latex] останется один элемент — значение выражения.

Код задачи на с++
Засчитанное решение на e-olymp

Related Images:

e-olymp 1309. Блоки строки

20/12/2015 by Павел Загинайло

Условие задачи

Блоком строки S в позиции i назовём наибольшую подстроку S, которая начинается в позиции i и совпадает с префиксом S. Длину блока в позиции 0 считать равной нулю.

Вычислить длины блоков строки S для всех позиций.

Входные данные

Единственная строка S (|S| ≤ 10⁶).

Выходные данные

В одной строке вывести длины блоков строки S для всех позиций, разделённые пробелом.

Тесты:

abaabaab
0 0 1 5 0 2 0

1 2	abaabaab 0 0 1 5 0 2 0

abaabaabbaaaaaaaaaaaabbbbbbbabaaaaaabababaaaaaaaabaaabaabaaaaaaaabaaabaaababababbab
0 0 1 5 0 1 2 0 0 1 1 1 1 1 1 1 1 1 1 1 2 0 0 0 0 0 0 0 4 0 1 1 1 1 1 3 0 3 0 4 0 1 1 1 1 1 1 1 4 0 1 1 7 0 1 4 0 1 1 1 1 1 1 1 4 0 1 1 4 0 1 1 3 0 3 0 3 0 2 0 0 2 0

1 2	abaabaabbaaaaaaaaaaaabbbbbbbabaaaaaabababaaaaaaaabaaabaabaaaaaaaabaaabaaababababbab 0 0 1 5 0 1 2 0 0 1 1 1 1 1 1 1 1 1 1 1 2 0 0 0 0 0 0 0 4 0 1 1 1 1 1 3 0 3 0 4 0 1 1 1 1 1 1 1 4 0 1 1 7 0 1 4 0 1 1 1 1 1 1 1 4 0 1 1 4 0 1 1 3 0 3 0 3 0 2 0 0 2 0

aaaaaaaaaaaaaaaaaaaaa
0 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

1 2	aaaaaaaaaaaaaaaaaaaaa 0 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

f2f
0 0 1

f2f

0 0 1

Код программы:

#include <iostream>
#include <cstring> 
using namespace std;
 
 
int main(){
	int zf[1000000];
	char s[1000000];
    scanf("%[^\n]%*c", s);
    int n = strlen(s);
    int right=0,left=0;
 
    for(int i=1; i < n; ++i){
           
            if(i<=right){
        		zf[i]=min(right-i+1,zf[i-left]);
            }
            while(s[zf[i]]==s[zf[i]+i]){
            	zf[i]++;
            }
            if(i+zf[i]-1>right){
    	        left=i;
                right=i+zf[i]-1;
            }
    }
 	
    for(int i=0; i < n; ++i){
    	cout << zf[i] << " ";	
    }
    
	return 0; 
}

#include <iostream>

#include <cstring>

using namespace std;

int main(){

int zf[1000000];

char s[1000000];

scanf("%[^\n]%*c", s);

int n = strlen(s);

int right=0,left=0;

for(int i=1; i < n; ++i){

if(i<=right){

zf[i]=min(right-i+1,zf[i-left]);

}

while(s[zf[i]]==s[zf[i]+i]){

zf[i]++;

}

if(i+zf[i]-1>right){

left=i;

right=i+zf[i]-1;

}

for(int i=0; i < n; ++i){

cout << zf[i] << " ";

}

return 0;

}

Алгоритм

В данной задаче из-за того, что наша строка может принимать длину до 10⁶ включительно, то необходим эффективный алгоритм. Я воспользовался алгоритмом вычисления Z-функции. Для начала мы заводим переменные left и right, в которых мы будем хранить координаты самого длинного отрезка, который совпадает с началом нашей строки. В начале цикла проверяем находится ли ячейчка, для которой ищется результат в отрезке между left и right. После прохождения цикла while, мы обновляем границы подстроки.

Код на ideone.com

Принятая задача на e-olymp.

Related Images:

e-olymp 2459. Юбилей Винни-Пуха

20/12/2015 by Павел Загинайло

Условие задачи

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

Входные данные

Входной файл содержит дату Юбилея Винни-Пуха в формате dd.mm.gggg. Гарантируется, что дата корректна.

Выходные данные

В выходной файл нужно вывести YES, если дата, читающаяся справа налево корректна, и NO в противном случае.

Код программы:

#include <iostream>
#include <string>
using namespace std;

string reverse(string s){
	string y;
	for (int i = 0; !s.empty(); i++){
		if (s.back() != '.'){
			y.push_back(s.back());
			s.pop_back();
		}
		if (s.back() == '.') s.pop_back();
	}
	return y;
}

bool is_leap(int year){
	bool leap;
	if ((year % 400) == 0) leap = true;
	else if ((year % 100) == 0) leap = false;
	else if ((year % 4) == 0) leap = true;
	else leap = false;
	return leap;
}

int get_days (int month, int year){
	int days;
	switch (month) {
		case 1:
		case 3:
		case 5:
		case 7:
		case 8:
		case 10:
		case 12:
		    days = 31;
		    break;
		case 4:
		case 6:
		case 9:
		case 11:
		    days = 30;
		    break;
		case 2:
			is_leap(year)?days = 29:days=28;
		    break;
		default:
		    days = -1;
    }
    return days;
}

int main() {
	string s,y;
	getline(cin, s);
	y = reverse(s);
	int day = stoi(y.substr(0,2));
	int month = stoi(y.substr(2,2));
	int year = stoi(y.substr(4,4));
	cout << (((month>=1)&&(month<=12)&&(day >= 1)&&(day <= (get_days(month, year))))?"YES":"NO");

	return 0;
}

#include <iostream>

#include <string>

using namespace std;

string reverse(string s){

string y;

for (int i = 0; !s.empty(); i++){

if (s.back() != '.'){

y.push_back(s.back());

s.pop_back();

}

if (s.back() == '.') s.pop_back();

}

return y;

}

bool is_leap(int year){

bool leap;

if ((year % 400) == 0) leap = true;

else if ((year % 100) == 0) leap = false;

else if ((year % 4) == 0) leap = true;

else leap = false;

return leap;

}

int get_days (int month, int year){

int days;

switch (month) {

case 1:

case 3:

case 5:

case 7:

case 8:

case 10:

case 12:

days = 31;

break;

case 4:

case 6:

case 9:

case 11:

days = 30;

break;

case 2:

is_leap(year)?days = 29:days=28;

break;

default:

days = -1;

}

return days;

}

int main() {

string s,y;

getline(cin, s);

y = reverse(s);

int day = stoi(y.substr(0,2));

int month = stoi(y.substr(2,2));

int year = stoi(y.substr(4,4));

cout << (((month>=1)&&(month<=12)&&(day >= 1)&&(day <= (get_days(month, year))))?"YES":"NO");

return 0;

}

Тесты

Входные данные	Выходные данные
23.02.2002	YES
20.02.2023	NO
20.12.2015	NO
20.12.2051	YES

Решение

Как только получили строку из стандартного ввода, воспользуемся функцией reverse(). Эта функция записывает нашу строку «задом наперед», в это же время удаляя символ ‘.’ из строки. Так как я точно знаю, что строка из ввода записана верно, то я могу не проверять остальные символы. Пользуясь этим же фактом я завел три переменные целочисленного типа: day, month, year. В новой строке присутствуют только цифры, поэтому я присваиваю каждой новой переменной соответствующие подстроки, после приведения типа string к типу int с помощью функции stoi(). В выводе проверяется соответствуют ли значения дня и месяца требованиям. День проверяется с помощью функции get_days(). Она позволяет получить количество дней в зависимости от месяца и года. В самой функции get_days() используется функция is_leap(), которая проверяет год на високосность и возвращается булевское значение. В зависимости от этого значения, изменяется значение количества дней в феврале — 28 или 29 соответственно. Когда наши числа прошли все проверки, то мы получаем на вывод «YES», если новая дата является корректной или «NO» в ином случае.

Код на ideone.com

Засчитанная задача на e-olymp.com

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: Алгоритмы на строках

Вычисление математических выражений

Related Images:

e-olymp 1309. Блоки строки

Related Images:

e-olymp 2459. Юбилей Винни-Пуха

Related Images: