Skip to content

Instantly share code, notes, and snippets.

@megabitsenmzq

megabitsenmzq/Calc.swift

Last active August 9, 2024 14:06
Show Gist options
  • Save megabitsenmzq/fa8e7ad1c9e67fdc42c3798c066709f8 to your computer and use it in GitHub Desktop.
Save megabitsenmzq/fa8e7ad1c9e67fdc42c3798c066709f8 to your computer and use it in GitHub Desktop.
Download ZIP
Swift algebra calculator with binary tree.
Raw
Calc.swift
import Foundation
class Calculator {
enum Operator: String, CaseIterable {
case add = "+"
case subtract = "-"
case multiply = "*"
case divide = "/"
case power = "^"
case squareRoot = "√"
case percent = "%"
static var allCasesString = allCases.reduce("", {$0 + $1.rawValue})
}
private static let numberSet = CharacterSet(charactersIn: "1234567890.")
static let allLegalCharacters = CharacterSet(charactersIn: "[]{}()" + Operator.allCasesString).union(numberSet)
func calc(_ string: String) -> Decimal? {
print("Raw: " + string)
let stringToParse = string.components(separatedBy: .whitespaces).joined()
guard Self.allLegalCharacters.isSuperset(of: CharacterSet(charactersIn: stringToParse)) else {
print("Illegal character")
return nil
}
let formulaArray = split(string: string)
guard isLegal(formulaArray) else {
print("Illegal calculation")
return nil
}
return realCalc(formulaArray)
}
func isDigit(charactersIn: String) -> Bool {
return Self.numberSet.isSuperset(of: CharacterSet(charactersIn: charactersIn))
}
private func split(string: String) -> [String] {
var formulaArray = [String]()
var numberBuffer = ""
for item in string {
let character = String(item)
if CharacterSet(charactersIn: "[]{}()" + Operator.allCasesString).isSuperset(of: CharacterSet(charactersIn: character)) {
if numberBuffer != "" { // Before a special character, it's a number.
formulaArray.append(numberBuffer)
numberBuffer = ""
}
formulaArray.append(character)
continue
}
numberBuffer += character
}
if numberBuffer != "" { // Append the last number if there is one.
formulaArray.append(numberBuffer)
}
// Turn all the brackets to "()".
for (index, item) in formulaArray.enumerated() {
if item == "{" || item == "[" || item == "[" {
formulaArray[index] = "("
}
if item == "}" || item == "]" {
formulaArray[index] = ")"
}
}
// Convert unary operator.
func makeUp(startWith: Int) {
for (index, item) in formulaArray.enumerated() {
if index < startWith { continue }
func insertZeroBefore() {
var leadingCount = 0
for i in 1...formulaArray.count - index - 1{
let item = formulaArray[index + i]
if item == "(" { leadingCount += 1 }
if item == ")" { leadingCount -= 1 }
if leadingCount == 0 {
formulaArray.insert(")", at: index + i + 1)
formulaArray.insert(contentsOf: ["(", "0"], at: index)
makeUp(startWith: index + 2)
return
}
}
}
func convertPercentToDivide() {
// % to /100
var leadingCount = 0
for i in 1...index {
let item = formulaArray[index - i]
if item == ")" { leadingCount += 1 }
if item == "(" { leadingCount -= 1 }
if leadingCount == 0 {
formulaArray[index] = Operator.divide.rawValue
formulaArray.insert(contentsOf: ["100",")"], at: index + 1)
formulaArray.insert("(", at: index - i)
makeUp(startWith: index + 2)
return
}
}
}
if formulaArray.count > index + 1 {
// Need to add 0 before.
if item == Operator.squareRoot.rawValue, index == 0 || formulaArray[index - 1] != "0" {
insertZeroBefore()
break
}
if item == "-" { // -1
if index == 0 || (!isDigit(charactersIn: formulaArray[index - 1]) && formulaArray[index - 1] != ")" && formulaArray[index - 1] != "-") {
insertZeroBefore()
break
}
}
}
if item == Operator.percent.rawValue, index != 0 {
convertPercentToDivide()
break
}
}
}
makeUp(startWith: 0)
return formulaArray
}
func isLegal(_ formulaArray: [String]) -> Bool {
if formulaArray.isEmpty {
print("Input is empty.")
return false
}
var leadingCount = 0
for (index, item) in formulaArray.enumerated() {
if item == "." {
return false
}
if item.components(separatedBy: ".").count > 2 {
return false
}
if Operator(rawValue: item) != nil {
if index == 0 || index == formulaArray.count - 1 {
print("An operator should not appear at the start or the end.")
return false
}
if Operator(rawValue: formulaArray[index + 1]) != nil {
print("An operator should not follow another.")
return false
}
}
if item == "(" {
leadingCount += 1
if index == formulaArray.count - 1 { return false }
if Operator(rawValue: formulaArray[index + 1]) != nil {
print("A left bracket should not follow by an operator.")
return false
}
if index != 0, isDigit(charactersIn: formulaArray[index - 1]) {
print("A left bracket should not follow a number.")
return false
}
for i in 1...3 {
if index + i < formulaArray.count, formulaArray[index + i] == ")" {
print("The distance between a pair of brackets must bigger than 2.")
return false
}
}
}
if item == ")" {
leadingCount -= 1
if index == 0 { return false }
if Operator(rawValue: formulaArray[index - 1]) != nil {
print("A right bracket should not follow an operator.")
return false
}
if index != formulaArray.count - 1, isDigit(charactersIn: formulaArray[index + 1]) {
print("A right bracket should not follow by a number.")
return false
}
}
}
if leadingCount != 0 {
print("The brackets are not paired.")
return false
}
return true
}
}
extension Calculator {
class Node: CustomStringConvertible {
var value: Decimal?
var `operator`: Operator?
var children: [Node] = []
weak var parent: Node?
init(operator: Operator?) {
self.operator = `operator`
}
init(value: Decimal) {
self.value = value
}
func add(child: Node) {
children.append(child)
child.parent = self
}
var description: String {
var text = "$"
if let value = value { text = "\(value)" }
if let op = `operator` { text = op.rawValue }
if !children.isEmpty {
text += " {" + children.map { $0.description }.joined(separator: ", ") + "} "
}
return text
}
}
}
// Real calc
extension Calculator {
func realCalc(_ formulaArray: [String]) -> Decimal? {
let start = CFAbsoluteTimeGetCurrent()
print("Input: \(formulaArray.joined())")
let fullFormula = fullBracketFormula(from: formulaArray)
print("Add brackets: \(fullFormula.joined())", "Spend time: " + String(format: "%.3f",CFAbsoluteTimeGetCurrent() - start))
guard let result = calcWithNode(fullFormula) else { return nil }
print("Result: \(result)", "Spend time: " + String(format: "%.3f",CFAbsoluteTimeGetCurrent() - start))
return result
}
func fullBracketFormula(from array: [String]) -> [String] {
var formulaArray = array
var lockedIndex = [Int]() // ...)*(... Only deal once.
func checkLeft(index: Int) -> Bool {
if lockedIndex.contains(index) {
return false
}
let hasCloseInLeading = index - 2 >= 0 && formulaArray[index - 2] == "(" // ...(42*...
let hasCloseInTrailing = index + 2 <= formulaArray.count - 1 && formulaArray[index + 2] == ")" // ...*42)...
if hasCloseInLeading && hasCloseInTrailing { // ...(42*42)...
return false
}
if formulaArray[index - 1] != ")"{ // ...)*...
if index + 1 < formulaArray.count, formulaArray[index + 1] == "(" {
lockedIndex.append(index)
}
formulaArray.insert("(", at: index - 1)
for (j, item) in lockedIndex.enumerated() {
if item >= index - 1 {
lockedIndex[j] += 1
}
}
return true
}
if formulaArray[index + 1] == "(" { // ...)*(...
lockedIndex.append(index)
}
// Add a left bracket before the nearest pair.
var trailingCount = 0
for i in 1...index {
let item = formulaArray[index - i]
if item == ")" { trailingCount += 1 }
if item == "(" { trailingCount -= 1 }
if trailingCount == 0 {
if index - i - 1 >= 0, formulaArray[index - i - 1] == "(" { // ...((42+42)*42)...
lockedIndex.append(index)
}
for (j, item) in lockedIndex.enumerated() {
if item >= index - i {
lockedIndex[j] += 1
}
}
formulaArray.insert("(", at: index - i)
return true
}
}
return false
}
func checkRight(index: Int) {
if formulaArray[index + 1] != "(" { // ...*(...
formulaArray.insert(")", at: index + 2)
return
}
// Add a right bracket after the nearest pair.
var leadingCount = 0
for i in 1...formulaArray.count - index {
let item = formulaArray[index + i]
if item == "(" { leadingCount += 1 }
if item == ")" { leadingCount -= 1 }
if leadingCount == 0 {
formulaArray.insert(")", at: index + i)
return
}
}
}
var lastIndex = 0
var isEnd = false
func loopFormula(opsString: [String]){
for index in lastIndex..<formulaArray.count {
let item = formulaArray[index]
if opsString.contains(item) {
if checkLeft(index: index) {
checkRight(index: index + 1) // Move one because of the new left bracket.
lastIndex = index + 1
return
}
}
if index == formulaArray.count - 1 {
isEnd = true
}
}
}
func loopFormula(ops: [Operator]) {
lockedIndex = []
lastIndex = 0
isEnd = false
while !isEnd {
loopFormula(opsString: ops.map({$0.rawValue}))
}
}
loopFormula(ops: [.power, .squareRoot])
loopFormula(ops: [.multiply, .divide])
loopFormula(ops: [.add, .subtract])
return formulaArray
}
func calcWithNode(_ formulaArray: [String]) -> Decimal? {
if formulaArray.count == 1, let theOnlyItem = formulaArray.first {
return Decimal(string: theOnlyItem)
}
var index = 0
func newNode() -> Node? {
let node = Node(operator: nil)
while index < formulaArray.count {
let item = formulaArray[index]
index += 1
if isDigit(charactersIn: item) {
node.add(child: Node(value: Decimal(string: item) ?? 0))
}
if let op = Operator(rawValue: item) {
node.operator = op
}
if item == "(" {
guard let newNode = newNode()?.value else {
print("No result form a child tree.")
return nil
}
node.add(child: Node(value: newNode))
}
if item == ")" || index == formulaArray.count - 1 {
if node.children.count == 1 {
return node.children.first
}
guard let first = node.children[0].value, let second = node.children[1].value else {
print("This should not happen.")
return nil
}
switch node.operator {
case .add:
return Node(value: first + second)
case .subtract:
return Node(value: first - second)
case .multiply:
return Node(value: first * second)
case .divide:
return Node(value: first / second)
case .power:
return Node(value: pow(first, (second as NSNumber).intValue))
case .squareRoot:
return Node(value: Decimal(sqrt((second as NSNumber).doubleValue)))
default:
print("Illegal operator")
return nil
}
}
}
return node
}
return newNode()?.value
}
}
Calculator().calc("(21^4+5)*√3+(34+(2^2-3)%*43)")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment