Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/*
Write a function that takes an expression and evaluates it. The expression is a different notation of an operand working over two operands. For example:
"2 + 5", in this prefix expression language could be written "(+ 2 5)"
The grammar for this expression syntax works like so:
expression := "( operator operand operand )"
operator: "*" | "+"
operand: expression | integer
examples:
( + 2 5 ) = 7
( * ( + 9 3 ) ( + 4 6 ) ) = 120
( + ( + 4 ( * 7 8 ) ) ( * 10 31 ) )
56 310
60 == 370
Assumptions:
- input is guaranteed to be valid.
- all characters in the input are separated by spaces.
*/
/*
expressions are:
- an operator (addition, multiplication)
- and two operands (Int, Int)
*/
indirect enum ArithmeticExpression {
case operand(Int)
case addition(ArithmeticExpression, ArithmeticExpression)
case multiplication(ArithmeticExpression, ArithmeticExpression)
}
enum ArithmeticExpressionError: Error {
case encodingError(String)
}
func evaluate(expression: String) -> Int {
var components = expression.components(separatedBy: " ")
let arithmeticExpression = try! encode(&components)
return eval(arithmeticExpression)
}
// Converts an array of Strings to a single ArithmeticExpression
func encode(_ components: inout [String]) throws -> ArithmeticExpression {
// Removes paren _or_ a number
let first = components.removeFirst()
if first != "(" {
return ArithmeticExpression.operand(Int(first)!)
}
// Removes the operator
let op = components.removeFirst()
let left = try encode(&components)
let right = try encode(&components)
components.removeFirst() // Removes last paren
switch op {
case "+":
return ArithmeticExpression.addition(left, right)
case "*":
return ArithmeticExpression.multiplication(left, right)
default:
throw ArithmeticExpressionError.encodingError("Operator: \(op) not supported!")
}
}
func eval(_ expression: ArithmeticExpression) -> Int {
switch expression {
case let .operand(value):
return value
case let .addition(left, right):
return eval(left) + eval(right)
case let .multiplication(left, right):
return eval(left) * eval(right)
}
}
// Some trivial tests:
evaluate(expression: "( + 2 5 )")
evaluate(expression: "( * ( + 9 3 ) ( + 4 6 ) )")
evaluate(expression: "( + ( + 4 ( * 7 8 ) ) ( * 10 31 ) )")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.