Вычисление математического выражения в C++

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

3 * 2 ^ 3 ^ 2 * 5

и должен оцениваться следующим образом:

3 * 2 ^ 3 ^ 2 * 5 = 3 * 2^(3 * 2) * 5 = 3 * 64 * 5 = 960.

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

Для текущего случая это будут: vector<int> operands = { 3, 2, 3, 2, 5 } и vector<char> operators = { '*', '^', '^', '*' }.

Это всего лишь пример, порядок операций может отличаться в том смысле, что умножение не всегда может быть первой/последней выполняемой операцией.

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

Решение было бы очень признательно.

введите здесь описание изображения


c++ parsing algorithm arithmetic-expressions
person user43389    schedule 30.09.2016    source источник
comment
Вы действительно имеете в виду 2^(3 * 2), а не 2^(3^2)?   -  person Robert Prévost    schedule 30.09.2016
comment
Нет, на самом деле это форма выражения, которую накладывает проблема, с этим ничего не поделаешь. 2 ^ 3 ^ 2 следует рассматривать как 2 ^ (3 * 2) = 2 ^ 6, в более общем случае y ^ x1 ^ x2 ^ ... ^ xn = y ^ (x1 * x2 * .... * xn).   -  person user43389    schedule 30.09.2016
comment
@ user43389 Нет, 2 ^ 3 ^ 2 следует оценивать как 2 ^ (3 ^ 2), = 2 ^ 9 = 512, и обратите внимание, что оно правоассоциативно. То, что вы написали, не имеет смысла.   -  person user207421    schedule 30.09.2016
comment
Я не говорю, что это имеет математический смысл, я просто сказал ранее, что это оценка, необходимая в этой задаче.   -  person user43389    schedule 30.09.2016
comment
И вместо того, чтобы голосовать против, вы вполне можете попросить разъяснений, если вы не понимаете, о чем вас спрашивают.   -  person user43389    schedule 30.09.2016
comment
Почему ^ один раз оценивается как ^, а другой раз как *?   -  person plasmacel    schedule 30.09.2016
comment
Это не имеет никакого смысла, не только математического смысла. В выражении есть непоследовательное использование ^. Вам придется написать контекстно-зависимый синтаксический анализатор и получить очень точное определение того, когда ^ становится *. Гораздо более вероятно, что либо вы, либо ваш клиент просто неправильно поняли. NB (а) я понимаю, о чем спрашивают, в той мере, в какой можно сказать, что кто-то понимает внутренние противоречия, и (б) у вас нет информации о том, кто проголосовал против вашего вопроса.   -  person user207421    schedule 30.09.2016
comment
Это алгоритмическая задача на hackerrank, и непоследовательное использование ^ в этом выражении можно просто рассматривать как следующее: В выражении формы y ^ x1 ^ x2 ^ ... ^ xn значение в левой части первого ^ устанавливает основу возведения в степень, в то время как другие n - 1 символы '^' генерируют показатель степени посредством последовательного умножения. Цепочка умножения останавливается, когда знак «*» встречается сразу после последнего множителя показателя степени.   -  person user43389    schedule 30.09.2016
comment
@ user43389 Вы можете делать такие вещи с шаблонами выражений. en.wikipedia.org/wiki/Expression_templates   -  person plasmacel    schedule 30.09.2016
comment
@EJP, бесконечно более вероятно, что вы не понимаете вопроса и прибегаете к поспешным суждениям, которые не имеют под собой никаких оснований. Проверьте проблему в недавно обновленном сообщении, я только заменил «**» на «^».   -  person user43389    schedule 30.09.2016
comment
Гораздо более вероятно, что hackerrank на самом деле ничего не знает. Но тогда я был писателем компилятора только с 1976 года.   -  person user207421    schedule 30.09.2016
comment
@EJP Выражение было бы совершенно согласованным, если бы оператор ^ (или **) был левоассоциативным. Это просто не так, в математике или в Python.   -  person Kyle Strand    schedule 30.09.2016
comment
Итак, да, похоже, что hackerrank облажался, но это это вопрос, который они (непреднамеренно) задали.   -  person Kyle Strand    schedule 30.09.2016
comment
@plasmacel Потому что (x ^ y) ^ z == x ^ (y * z), и похоже, что тот, кто написал этот вопрос для hackerrank, ошибочно полагает, что возведение в степень является левоассоциативным (как и большинство других математических операторов).   -  person Kyle Strand    schedule 30.09.2016
comment
Это просто синтаксис. Люди придумывают любой синтаксис, который им нравится, и могут определять его значение так, как им нравится. Это может быть не так, как вы сделали бы это. Жесткий. Если синтаксис хорошо определен, для него легко написать синтаксический анализатор и оценщик. См. stackoverflow.com/questions/2245962/. Re OPs представление операторов и операндов в виде чередующихся значений в векторе: это довольно ограничивает (возможно, не для этой проблемы). Представь - как унарный оператор; как бы он представил это в своем векторе?   -  person Ira Baxter    schedule 30.09.2016

Ответы (2)


arrow_upward
1
arrow_downward

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

Кроме того, я бы не стал хранить все выражение в каком-то векторизованном формате; Я не вижу полезной причины для этого.

person Kyle Strand    schedule 30.09.2016
comment
Это именно то, что я сделал (с точки зрения мышления), но я, кажется, как-то испортил реализацию (она работает только в данном тестовом примере). Приятно знать, что это путь, реализация была бы действительно хороша, если бы у вас было время. Спасибо - person user43389; 30.09.2016
comment
@user43389 user43389 В каких тестовых случаях ваша реализация дает сбой? Поскольку вся проблема левой ассоциативности не упоминается в исходной задаче, и мы только предполагаем, что это то, что ожидается от решения, основанного на самом тестовом примере, вполне возможно, что пример теста просто неверен. - person Kyle Strand; 30.09.2016
comment
К сожалению, тестовые случаи скрыты. Но, судя по количеству успешных заявок от других людей, я думаю, что проблема действительно решаема, даже с учетом плохо написанного текста. - person user43389; 30.09.2016
comment
@user43389 user43389 Ну, вы пытались отправить решение, которое просто оценивает выражения с правильным математическим приоритетом (то есть с правоассоциативным возведением в степень)? - person Kyle Strand; 30.09.2016
comment
@ user43389 Я никогда не пробовал hackerrank; у вас есть постоянная ссылка на вопрос, чтобы я мог попробовать отправить решение? - person Kyle Strand; 30.09.2016

arrow_upward
1
arrow_downward

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

person plasmacel    schedule 30.09.2016