codedokode/Задача на калькулятор.md

## Задача на калькулятор.md

      
    Raw
  

              Задача на калькулятор.md
            
          
    Задача про калькулятор на ООП


Уровень: джуниор с широким кругозором и целеустремленностью
Ключевые слова для гугления подсказок: грамматики, токенайзер, парсер, recursive descent, обратная польская запись, AST
Время: 2-3 дня

Ты можешь использовать любой понравившийся язык и библиотеки, но, пожалуйста, не ищи готовые решения и не копипасть код (можно найти решение на другом языке, разобраться, как оно работает, и написать своими словами, если сам додуматься не смог). Гуглить и использовать алгоритмы можно.
Задание: сделать программу-калькулятор, считающую значение математического выражения. Выражение содержит целые (123) и дробные числа (13.45), скобки, операции +, -, /, *, ^ (возведение в степень). В выражении должен соблюдаться приоритет операций:

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

Пример расстановки приоритетов: выражение 2 + 3 * 5 ^ 2 ^ 2 / 3 считается в таком порядке:
2 + (3 * (5 ^ (2 ^ 2)) / 3)

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


программа при вычислении выражения не должна округлять дроби. Например, выражение 1/3 + 1 должно давать 4/3 (или 1 + 1/3), а не округлять результат до 1.333334. Только десятичные дроби нужно писать не в виде 16/10, а в виде 1.6


программа должна корректно писать сообщение об ошибке при попытке поделить на 0


Примеры выражений для проверки калькулятора:
2 + 3            >  5
4 - 3            >  1
2 + (-3)         > -1
4 * 5            > 20
6/4              > 3/2
1.2 + 1/2        > 1.7
1/(-3)           > -1/3
0.5 + 0.2        > 0.7
3 ^ 2 ^ 2        > 81
17654/342        > 8827/171
2/3 ^ 2          > 2/9
(2/3) ^ 2        > 4/9
(2 + 3) / (2 - 2)> Ошибка: делить на ноль (5/0) нельзя
2 + 345 + + + + 6> Ошибка: выражение записано неправильно

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


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


сначала выражение надо разбить на набор токенов (отдельных чисел и знаков, без пробелов), а дальше есть 2 варианта:

с помощью recursive descent parser преобразовать выражение в AST и вычислить
перевести выражение в обратную польскую нотацию с помощью алгоритма сортировочной станции, и вычислить получившееся выражение


Чтобы дроби не терялись, достаточно при вычислении хранить все числа в виде дробей и делать операции над обеими частями


Сократить дробь вроде 16/8 легко, найдя наибольший общий делитель для двух чисел. Алгоритм нахождения НОД придумали еще древние греки, так что и ты его осилишь, я уверен.


При выводе дроби можно использовать подход: дробь вида X/1 выводить как обычное число.


Кто-нибудь хочет попробовать свои силы?
Пример довольно-таки нечитаемого решения на Питоне: http://ideone.com/58awxP
Решение на PHP с ООП от Калькулятор-куна (тем, кто решает, не подглядывать): http://ideone.com/T0AfO