Условие задачи:
Пусть дана строка, которая является математическим выражением, содержащим числа, переменные и различные операции. Требуется вычислить его значение.
Помимо создания прототипа работы элементарного калькулятора, рассмотрим решение одной из подзадач — «Многочлен», найденную на просторах сайта 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-3*x^2+x^2+100*x^3-2*x | -7 | -34393 |
| -2*x^2+16*x^3-x | (-3)^4 | 8489853 |
| x^2-5*x+15-8*x^4 | 0 | 15 |
Код на с++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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
— «решать данные выражения»? Решают уравнения, неравенства и другие задачи. Выражения можно вычислять. Поправьте, пожалуйста.
— Теперь по сути. Вы проделали огромную работу, которая в том числе позволяет вычислять значения многочленов. Но Вы решили гораздо более сложную задачу чем разбор того простого формата, который требовался в задаче 1652. Пожалуйста, второй вариант для char * сделайте предельно коротким. Вам всего-то нужна функция, которая читает целое число, потом не читает *x^ и читает второе число. И так продолжается пока (например, strpbrk) находит + или -. Конечно, там будут варианты т.к. числа могут отсутствовать, но пара условных операторов решит и эту проблему.
— И наконец, самый главный вопрос. У вас вроде задача 1074, а не 1652?
Здравствуйте, привела творческую задачу к более общему виду и исправила лексические ошибки.
Отлично. В таком варианте статья мне нравится.