Текст Домашнего задания на английском языке доступен на iTunes в пункте “Developing iOS 8 app: Programming: Project 2″. Текст Домашнего задания на русском языке доступен на Результаты выполнения задания можно обсуждать на форуме Swift[ru] . Ваше решение может быть лучше и интереснее. Выкладывайте его в Github, давайте ссылку на Dropbox или используйте другие системы управления версиями. Xcode работает напрямую с Github.
Пункт 1 дополнительный
Сделайте так, чтобы ваша description имела как можно меньше круглых скобок для бинарных операций.
Теоретическая часть согласно подсказке в Задании 2 потребует добавления концепции “приоритета (precedence) операций” в Op вашего CalculatorBrain.
Заметим, что все нижеприведенные рассуждения касаются только перевода нашего стэка, записанного в форме обратной польской записи (RPN), не требующей применения скобок, в инфиксную форму со скобками. Инфиксная форма нужна только для представления описания стэка в привычной для пользователя форме var description и не влияет на вычисления нашего калькулятора.
Приоритет, ранг или старшинство операции или оператора согласно Wikipedia — формальное свойство оператора/операции, влияющее на очередность его выполнения в выражении с несколькими различными операторами при отсутствии явного (с помощью скобок) указания на порядок их вычисления. Например, операцию умножения обычно наделяют бо́льшим приоритетом, чем операцию сложения, поэтому в выражении X + Y * Z будет получено сначала произведение Y * Z , а потом уже сумма. Если порядок операций именно такой, то никаких скобок не требуется. Если нужен другой порядок операции, например сначала сумма (X + Y), а потом произведение , то применяют круглые скобки (X + Y) * Z.
У нас порядок операций строго определен стэком операндов и операций, который моделируется перечислением enum Op. Поэтому, нам лишь приходится выбирать: ставить круглые скобки или нет, в зависимости от соотношения приоритетов между приоритетом «родительской» операции (в нашем примере *) и приоритетом операции для операнда (в нашем примере +). Если приоритетом «родительской» операции выше приоритетом операции для операнда, то мы должны использовать круглые скобки, а в противном случае — нет.
Операции могут иметь одинаковый приоритет, тогда они вычисляются по правилу ассоциативности, установленному для этих операций. Правило означает как будут выполняться операции в отсутствии скобок. Есть правая и левая ассоциативность операции. Большинство привычных нам операций имеют левую ассоциативность. Это означает, что операции начинают выполняться слева направо. Например, для операции сложения в выражении X-Y+Z сначала будет вычисляться X-Y, а затем (X-Y) + Z. Если нам нужен другой порядок выполнения, то мы должны поставить круглые скобки. Например, в этом случае X-(Y+Z). Однако если у нас X+Y+Z, то результат не зависит от порядка группировки : (X+Y)+Z и X+(Y+Z) дают одинаковый результат. В этом случае важно, обладает ли операция свойством коммутативность, то есть зависит ли результат вычисления от перемены мест операндов. Вычитание не является коммутаторной операцией и нам иногда придется поставить круглые скобки в случае одинаковых приоритетов. Сложение является коммутаторной операцией и нам никогда не придется ставить круглые скобки в случае одинаковых приоритетов. Такая же ситуация складывается с парой Умножение и Деление. Причем если операция не является коммутаторной — Вычитание и Деление — то окружать круглыми скобками нужно только операнд, стоящий справа. В нашем примере X-(Y+Z) для операции Вычитание операнд (Y+Z) является правым операндом и должен быть окружен круглыми скобками. В случае X — W — (Y+Z) для центральной операции Вычитания операндами будут X — W и (Y+Z) , но только правый операнд (Y+Z) нуждается в круглых скобках.
Отвлекаясь в сторону, напомню, что операторы в Swift также имеют свойства preference и associativity. Например,
infix operator ** { associativity left precedence 160 }Наибольшее количество круглых скобок в нашем калькуляторе плодится в бинарных операциях, поэтому постараемся в первую очередь избавиться от них.
Добавляем две новые вычисляемые переменные в перечисление enum Op в нашем CalculatorBrain
var precedence: Int
var commutative: Bool
Для бинарных операций эти значения будут задаваться при определении операций, а для других вариантов перечисления enum Op будут возвращаться значения по умолчанию: для precedence — максимальное целое значение Int.max, а для commutative — true:
Для операций умножения и деления устанавливаем precedence — 2, а для сложения и вычитания —1. Для всех операций, кроме вычитания и деления устанавливаем commutative — true, а для вычитания и деления — false.
В возвращаемый кортеж вспомогательного рекурсивного метода private description метода добавляем дополнительный параметр — приоритет (precedence) родительской операции precedence: Int. Бинарные операции проверяют свой текущий приоритет и сравнивают его с приоритетом операций аргументов. Если приоритет текущей операции выше приоритета операции аргумента, то мы заключаем соответствующий аргумент в круглые скобки. Если приоритет текущей операции равен приоритету операции аргумента, то мы анализируем коммутативность commutative текущей операции и в зависимости от этого, добавляем или нет круглые скобки. Второй операнд operand2, который затем становится первым, можно на коммутативность не проверять, то есть для этого операнда мы не будем использовать круглые скобки при равенстве приоритетов.
Кроме того, понятно, что на выходе этой рекурсивный функции result будет обычной строкой String, а не Optional, так как мы нигде не возвращаем nil. Это упростит некоторые выражения. Скорректируются две non-private переменные var description и var description1 и рекурсивный метод более высоко порядка для расчета нескольких законченных выражений descParts (в учебных целях я оставила в коде два варианта создания инфиксного представления нашего стэка: description c применением обычной do…while конструкции и description1 с использованием еще одного рекурсивный метода).
Были проведены многочисленные тесты на правильность формирования переменной description. Среди них особенно выделяются те, которые не дают правильный результат, если не учесть «коммутативность» операций.
Стэк 3 ↵ 4 ↵ 5 + — должен давать 3 — ( 5 + 4), а не 3 — 5 + 4
Стэк 3 ↵ 4 ↵ 5 × ÷ — должен давать 3 ÷ (5 × 4), а не 3 ÷ 5 × 4
Стэк 10 ↵ 5↵ 2 — — — должен давать 10 — (5 — 2), а не 10 — 5 — 2
Стэк 3 ↵ 5↵ — 7 ↵ 8↵ — — должен давать 3 − 5 − (7 − 8), а не 3 − 5 − 7 − 8
Код можно посмотреть на Github.
Для тестирования необходимо разместить тесты в файле CalculatorBrainTests и вместо запуска приложения кнопкой Run, нужно использовать Test
Полный список тестов на правильность формирования description приведен ниже.
[objc]
class CalculatorBrainTests: XCTestCase {
private var brain = CalculatorBrain()
func testPushOperandVariable() {
XCTAssertNil(brain.pushOperand("x"))
brain.setVariable ("x", value: 5.2)
XCTAssertEqual(5.2, brain.pushOperand("x")!)
XCTAssertEqual(10.4, brain.performOperation("+")!)
}
func testDescription() {
// cos(10)
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(10)!, 10)
XCTAssertTrue(brain.performOperation("cos")! — -0.839 < 0.1)
XCTAssertEqual(brain.displayStack(), "10.0 cos")
// 3 — 5
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertEqual(brain.pushOperand(5)!, 5)
XCTAssertEqual(brain.performOperation("−")!, -2)
XCTAssertEqual(brain.description, "3 − 5")
// 23.5
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(23.5)!, 23.5)
XCTAssertEqual(brain.description, "23.5")
// π
brain = CalculatorBrain()
XCTAssertEqual(brain.performOperation("π")!, M_PI)
XCTAssertEqual(brain.description, "π")
// x
brain = CalculatorBrain()
XCTAssertNil(brain.pushOperand("x"))
XCTAssertEqual(brain.description, "x")
// √(10) + 3
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(10)!, 10)
XCTAssertTrue(brain.performOperation("√")! — 3.162 < 0.1)
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertTrue(brain.performOperation("+")! — 6.162 < 0.1)
XCTAssertEqual(brain.description, "√(10) + 3")
// √(3 + 5)
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertEqual(brain.pushOperand(5)!, 5)
XCTAssertEqual(brain.performOperation("+")!, 8)
XCTAssertTrue(brain.performOperation("√")! — 2.828 < 0.1)
XCTAssertEqual(brain.description, "√(3 + 5)")
// 3 + (5 + 4) —> 3 + 5 + 4
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertEqual(brain.pushOperand(5)!, 5)
XCTAssertEqual(brain.pushOperand(4)!, 4)
XCTAssertEqual(brain.performOperation("+")!, 9)
XCTAssertEqual(brain.performOperation("+")!, 12)
XCTAssertEqual(brain.description, "3 + 5 + 4")
// (3 + 5) * 6
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertEqual(brain.pushOperand(5)!, 5)
XCTAssertEqual(brain.performOperation("+")!, 8)
XCTAssertEqual(brain.pushOperand(6)!, 6)
XCTAssertEqual(brain.performOperation("×")!, 48)
XCTAssertEqual(brain.description, "(3 + 5) × 6")
// √(3 + √(5)) ÷ 6
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertEqual(brain.pushOperand(5)!, 5)
XCTAssertTrue(brain.performOperation("√")! — 2.236 < 0.1)
XCTAssertTrue(brain.performOperation("+")! — 5.236 < 0.1)
XCTAssertTrue(brain.performOperation("√")! — 2.288 < 0.1)
XCTAssertEqual(brain.pushOperand(6)!, 6)
XCTAssertTrue(brain.performOperation("÷")! — 0.381 < 0.1)
XCTAssertEqual(brain.description, "√(3 + √(5)) ÷ 6")
// ? + 3
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertNil(brain.performOperation("+"))
XCTAssertEqual(brain.description, "? + 3")
// √(3 + 5), cos(π)
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertEqual(brain.pushOperand(5)!, 5)
XCTAssertEqual(brain.performOperation("+")!, 8)
XCTAssertTrue(brain.performOperation("√")! — 2.828 < 0.1)
XCTAssertEqual(brain.performOperation("π")!, M_PI)
XCTAssertEqual(brain.performOperation("cos")!, -1)
XCTAssertEqual(brain.description, "√(3 + 5), cos(π)")
// 3 * (5 + 4)
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertEqual(brain.pushOperand(5)!, 5)
XCTAssertEqual(brain.pushOperand(4)!, 4)
XCTAssertEqual(brain.performOperation("+")!, 9)
XCTAssertEqual(brain.performOperation("×")!, 27)
XCTAssertEqual(brain.description, "3 × (5 + 4)")
// 3 — (5 + 4) commutative test
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertEqual(brain.pushOperand(5)!, 5)
XCTAssertEqual(brain.pushOperand(4)!, 4)
XCTAssertEqual(brain.performOperation("+")!, 9)
XCTAssertEqual(brain.performOperation("−")!, -6)
XCTAssertEqual(brain.description, "3 − (5 + 4)")
// 3 / (5 × 4) commutative test
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertEqual(brain.pushOperand(5)!, 5)
XCTAssertEqual(brain.pushOperand(4)!, 4)
XCTAssertEqual(brain.performOperation("×")!, 20)
XCTAssertEqual(brain.performOperation("÷")!, 0.15)
XCTAssertEqual(brain.description, "3 ÷ (5 × 4)")
// (3 + 5) + (7 + 8)
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertEqual(brain.pushOperand(5)!, 5)
XCTAssertEqual(brain.performOperation("+")!, 8)
XCTAssertEqual(brain.pushOperand(7)!, 7)
XCTAssertEqual(brain.pushOperand(8)!, 8)
XCTAssertEqual(brain.performOperation("+")!, 15)
XCTAssertTrue(brain.performOperation("÷")! — 0.53333 < 0.1)
XCTAssertEqual(brain.description, "(3 + 5) ÷ (7 + 8)")
// 3 — 5 — (7 — 8) commutative test
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertEqual(brain.pushOperand(5)!, 5)
XCTAssertEqual(brain.performOperation("−")!, -2)
XCTAssertEqual(brain.pushOperand(7)!, 7)
XCTAssertEqual(brain.pushOperand(8)!, 8)
XCTAssertEqual(brain.performOperation("−")!, -1)
XCTAssertEqual(brain.performOperation("−")!, -1)
XCTAssertEqual(brain.description, "3 − 5 − (7 − 8)")
// (3 + 5) × (7 + 8)
brain = CalculatorBrain()
XCTAssertEqual(brain.pushOperand(3)!, 3)
XCTAssertEqual(brain.pushOperand(5)!, 5)
XCTAssertEqual(brain.performOperation("+")!, 8)
XCTAssertEqual(brain.pushOperand(7)!, 7)
XCTAssertEqual(brain.pushOperand(8)!, 8)
XCTAssertEqual(brain.performOperation("+")!, 15)
XCTAssertEqual(brain.performOperation("×")!, 120)
XCTAssertTrue(brain.performOperation("√")! — 10.9544 < 0.1)
XCTAssertEqual(brain.description, "√((3 + 5) × (7 + 8))")
}
}
[/objc]
Возможен и немного другой рекурсивный алгоритм description, убирающий лишние круглые скобки с помощью приоритетов и коммутативности. Если мы вернемся к нашему примеру X — (Y+Z), то мы можем проводить анализ приоритетов как находясь в родительской операции (в нашем случае «-«), так и в операции операнда (в нашем случае «+». В первом случае мы при равенстве приоритетов анализируем коммутативность текущей родительской операции и заключаем в круглые скобки операнды. Во втором случае мы анализируем коммутативность родительской операции, которая должна быть передана на вход description, и в круглые скобки придется заключать весь результат операции операнда.
У нас работает первый вариант этого алгоритма.
В учебных целях привожу второй вариант алгоритма, который в коде на Github закомментирован.
Для использования этого метода description необходимо в var precedence: Int
возвращать вместо return Int.max другое return 0
Но чем интересен этот вариант ? При вызове этого метода description (remainder) в переменной var description: String можно не добавлять дополнительный аргумент, так как будет использоваться значение дополненного аргумент по умолчанию opPrev: Op = .Variable («x»), которое имеет precedence = 0 и commutative = true. Это демонстрирует гибкие возможности Swift добавлять новые аргументы в функции, не меняя обращения к ним.
Код для Swift 1.2 и iOS 8.4 можно посмотреть на Github.
Код для Swift 2.0 и iOS 9 можно посмотреть на Github.
Продолжение следует…
Добрый вечер!
Поясни пожалуйста что за калдунство происходит когда мы добавляем переменные precedence и commutative в тип Op. Мы добавляем к бинарной операции 2 параметра типа Int и Bool:
BinaryOperation(String, Int, Bool, (Double, Double ) -> Double)
Затем присваиваем им значения:
lernOp(Op.BinaryOperation(«÷», 2, false, {$1 / $0})).
Мне не понятно каким образом свифт понимает что значения «2» и «false» относятся к precedence и commutative соответсвенно. Сначала я думал что сопоставление происходит по типу передаваемых данных. Я добавил в Op ещё одно свойство типа Int, но свифт по прежнему безошибочно присваивает 2 в precedence.
Объясни те пожалуйста как это работает, или дайте ссылку где можно изучит этот момент подробнее.
Спасибо!
Никакой магии нет. Потому что есть readonly вычисляемые свойства
var precedence: Int {get {
switch self {
case .BinaryOperation(_, let precedence, _, _, _):
return precedence
default:
return Int.max
}
}
}
var commutative: Bool {
get {
switch self {
case .BinaryOperation(_, _ , let commutative, _, _):
return commutative
default:
return true
}
}
}
которые для каждой.BinaryOperation(_, _ , let commutative, _, _) возвращают соответственно второе и третье ассоциативные значения.