I am writing a Swift program that will solve post script equations. I have two Classes: ExpressionTree, and ExpressionTreeLeaf, which inherits Expression Tree. In the ExpressionTree Class, I need a method that solves the tree. I also need to override that function in the ExpressionTreeLeaf Class to just return the data of the leaf. I'll give some code for context:
ExpressionTree class:
class ExpressionTree{
let Left: ExpressionTree?
let Right: ExpressionTree?
let Data: String
// constructor for tree with known left and right
init(Data: String, Left: ExpressionTree? = nil, Right: ExpressionTree? = nil) {
self.Data = Data
self.Left = Left
self.Right = Right
}
// constructor for tree with only data
init(Data:String){
self.Data = Data
self.Left = nil
self.Right = nil
}
// this method returns double regardless of inputs
func ApplyOp(val1: Double, val2: Double, op:String) -> Double?{
switch op {
case " ":
return val1 val2
case "-":
return val1 - val2
case "*":
return val1 * val2
case "/":
if( val2 != 0 ){
return val1 / val2
}
else{
return nil
}
default:
return nil
}
}
func Solve() -> Double{
return ApplyOp(val1: (Left?.Solve())!, val2: (Right?.Solve())!, op: Data)!
}
ExpressionTreeLeaf Class:
class ExpressionTreeLeaf: ExpressionTree {
init(_ Data: String) {
super.init(Data: "\(Data)")
}
func Solve() -> String {
return Data
}
}
My question is this: While using the debugger, I never seem to go into the ExpressionTreeLeaf constructor. I recursively go into the same solve method, and get error because the parameters are in the wrong place, causing them to be defaulted to 0.0. How to I get the recursive call to go into the ExpressionTreeLeaf class, so that when called, it will return the data of the leaf? Thank you
EDIT: here is the method to make the Tree: expression is in postfix notation
func MakeTree(expression: [String]) -> ExpressionTree{
let precedance: [String: Int] = [" ": 1 , "-": 1, "*": 2, "/": 2]
var stack: Deque<ExpressionTree> = []
for piece in expression {
if(isNumber(check: "\(piece)")){
let tree: ExpressionTreeLeaf = ExpressionTreeLeaf("\(piece)")
stack.append(tree)
}
else if precedance["\(piece)"] != nil{
let tree1: ExpressionTree = stack.removeLast()
let tree2: ExpressionTree = stack.removeLast()
let newTree: ExpressionTree = ExpressionTree(Data: "\(piece)", Left: tree1, Right: tree2)
stack.append(newTree)
}
}
return stack.removeLast()
}
CodePudding user response：
The problem is solved. I originally had incorrect return types which was not allowing me to call functions properly.
CodePudding user response：
I realize you solved your problem but I would suggest using protocols rather than inheritance. Also, in Swift, value types such as enums and structs are preferred over classes.
First, here are a couple of utils for parsing the expression:
extension String {
var isDigits: Bool {
onlyConsistsOf(charactersIn: .decimalDigits)
}
var isMathOperation: Bool {
onlyConsistsOf(charactersIn: .init(charactersIn: " -*/"))
}
func onlyConsistsOf(charactersIn set: CharacterSet) -> Bool {
rangeOfCharacter(from: set.inverted) == nil
}
}
extension Character {
var isDigit: Bool {
String(self).isDigits
}
var isMathOperation: Bool {
String(self).isMathOperation
}
}
Now we can get down to the nitty gritty. Let's start with a protocol:
protocol Evaluatable {
func evaluate() -> Double
}
Wether we are dealing with a an operation or an operand we can treat the types the same with protocol conformance. Notice how the Operand and Operation only store properties that they need. In your implementation your ExpressionTreeLeaf inherited from ExpressionTree even though it didn't need the Left or Right properties.
struct Operand: Evaluatable {
let value: Double
func evaluate() -> Double {
value
}
}
struct Operation: Evaluatable {
let lhs: Evaluatable
let rhs: Evaluatable
let op: Character
private var operation: (Double, Double) -> Double {
switch op {
case " ":
return ( )
case "-":
return (-)
case "*":
return (*)
case "/":
return (/)
default:
fatalError("Bad op: \(op)")
}
}
func evaluate() -> Double {
operation(lhs.evaluate(), rhs.evaluate())
}
}
Now let's create a top-level Tree type to store the root component to be evaluated. If you like, you can even make Tree conform to Evaluatable.
struct Tree: Evaluatable {
let root: Evaluatable
func evaluate() -> Double {
root.evaluate()
}
}
This factory method constructs the Tree using the same stack-based algorithm you posted. The stack is declared using the protocol we defined so we can store Operations or Operands.
enum TreeFactory {
static func makeTree(fromExpression expression: String) -> Evaluatable {
var stack: [Evaluatable] = []
for symbol in expression {
if symbol.isDigit {
stack.append(Operand(value: Double(String(symbol)) ?? 0.0))
} else if symbol.isMathOperation {
let rhs = stack.removeLast()
let lhs = stack.removeLast()
stack.append(Operation(lhs: lhs, rhs: rhs, op: symbol))
} else {
stack.removeAll()
break
}
}
return Tree(root: stack.isEmpty ? Operand(value: .zero) : stack.removeLast())
}
}
Let's conform to CustomStringConvertible for debugging purposes:
extension Operand: CustomStringConvertible {
var description: String { "\(value)" }
}
extension Operation: CustomStringConvertible {
var description: String { "(\(lhs) \(op) \(rhs))" }
}
extension Tree: CustomStringConvertible {
var description: String { "Tree: \(root) = \(evaluate())" }
}
Let's try this out:
let expression = "32 32 *3*2 1-2/"
let tree = TreeFactory.makeTree(fromExpression: expression)
print(tree)
Which results in:
Tree: ((((((3.0 2.0) * (3.0 2.0)) * 3.0) 2.0) - 1.0) / 2.0) = 38.0
This problem can also be solved using an enum rather than with structs. Here's an alternate solution.
indirect enum TreeNode: Evaluatable {
case operand(Double)
case operation(Character, TreeNode, TreeNode)
case root(TreeNode)
func evaluate() -> Double {
switch self {
case .operand(let value):
return value
case .operation(let op, let lhs, let rhs):
switch op {
case " ":
return lhs.evaluate() rhs.evaluate()
case "-":
return lhs.evaluate() - rhs.evaluate()
case "*":
return lhs.evaluate() * rhs.evaluate()
case "/":
return lhs.evaluate() / rhs.evaluate()
default:
return .zero
}
case .root(let node):
return node.evaluate()
}
}
}
Let's make another factory method to create an enum-based tree:
extension TreeFactory {
static func makeNodeTree(fromExpression expression: String) -> Evaluatable {
var stack: [TreeNode] = []
for symbol in expression {
if symbol.isDigit {
stack.append(.operand(Double(String(symbol)) ?? 0.0))
} else if symbol.isMathOperation {
let rhs = stack.removeLast()
let lhs = stack.removeLast()
stack.append(.operation(symbol, lhs, rhs))
} else {
stack.removeAll()
break
}
}
return TreeNode.root(stack.isEmpty ? .operand(.zero) : stack.removeLast())
}
}
Let's make our TreeNode debug friendly:
extension TreeNode: CustomStringConvertible {
var description: String {
switch self {
case .operand(let value):
return "\(value)"
case .operation(let op, let lhs, let rhs):
return "(\(lhs) \(op) \(rhs))"
case .root(let node):
return "Tree: \(node) = \(evaluate())"
}
}
}
And now to test it out:
let expression = "32 32 *3*2 1-2/"
let nodeTree = TreeFactory.makeNodeTree(fromExpression: expression)
print(nodeTree)
Here are the results:
Tree: ((((((3.0 2.0) * (3.0 2.0)) * 3.0) 2.0) - 1.0) / 2.0) = 38.0