Math expression parsing using Point-Free's swift-parsing library. Expands on code found in the infix-operator branch.

Arithmetic.swift

import Parsing
import XCTest
import Foundation

#if canImport(Darwin)
import Darwin.C
#elseif canImport(Glibc)
import Glibc
#endif

public enum Associativity {
  case left
  case right
}

/// Parser for infix operators. Takes a parser for operators to recognize and an operator for values to use with the
/// operator which could include operations of that are of lower precedence than those parsed by the first parser. Based on
/// code found in swift-parsing infix-operator branch.
public struct InfixOperator<Operator, Operand>: Parser
where
Operator: Parser,
Operand: Parser,
Operator.Input == Operand.Input,
Operator.Output == (Operand.Output, Operand.Output) -> Operand.Output
{
  @usableFromInline
  let _parser: (inout Operand.Input) -> Operand.Output?

  /**
   Construct new parser

   - parameter operator: the parser that recognizes valid operators at a certain precedence level
   - parameter associativity: the associativity for these operators
   - parameter operand: the parser for values to provide to the operator
   */
  @inlinable
  public init(_ operator: Operator, associativity: Associativity, higher operand: Operand) {
    switch associativity {
    case .left: self._parser = { Self.leftAssociative(input: &$0, operand: operand, operator: `operator`) }
    case .right: self._parser = { Self.rightAssociative(input: &$0, operand: operand, operator: `operator`) }
    }
  }

  /**
   Implementation of Parser method. Looks for "operand operator operand" sequences

   - parameter input: the input stream to parse
   - returns: the next output value found in the stream, or nil if no match
   */
  @inlinable
  public func parse(_ input: inout Operand.Input) -> Operand.Output? {
    self._parser(&input)
  }

  @usableFromInline
  static func leftAssociative(input: inout Operand.Input, operand: Operand, operator: Operator) -> Operand.Output? {
    guard var lhs = operand.parse(&input) else { return nil }
    var rest = input
    while
      let operation = `operator`.parse(&input),
      let rhs = operand.parse(&input)
    {
      rest = input
      lhs = operation(lhs, rhs)
    }
    input = rest
    return lhs
  }

  @usableFromInline
  static func rightAssociative(input: inout Operand.Input, operand: Operand, operator: Operator) -> Operand.Output? {
    var lhs: [(Operand.Output, Operator.Output)] = []
    while let rhs = operand.parse(&input) {
      guard let operation = `operator`.parse(&input)
      else {
        return lhs.reversed().reduce(rhs) { rhs, pair in
          let (lhs, operation) = pair
          return operation(lhs, rhs)
        }
      }
      lhs.append((rhs, operation))
    }
    return nil
  }
}

/// Parser for addition / subtraction operations
private let additionAndSubtraction = InfixOperator(
  Skip(Whitespace())
    .take(OneOfMany(
      "+".utf8.map { (+) },
      "-".utf8.map { (-) }
    )),
  associativity: .left,
  higher: multiplicationAndDivision
)

/// Parser for multiplication / division operations
private let multiplicationAndDivision = InfixOperator(
  Skip(Whitespace())
    .take(OneOfMany(
      "*".utf8.map { (*) },
      "/".utf8.map { (/) }
    )),
  associativity: .left,
  higher: exponent
)

/// Parser for exponentiation operations
private let exponent = InfixOperator(
  Skip(Whitespace())
    .take("^".utf8.map { pow }),
  associativity: .left,
  higher: factor
)

/// Parser for parenthetical expression or a literal double value
private let factor: AnyParser<Substring.UTF8View, Double> = Skip(Whitespace())
  .take("(".utf8)
  .take(Lazy { additionAndSubtraction })
  .skip(Whitespace())
  .take(")".utf8)
  .map { $0.1 }
  .orElse(
    Skip(Whitespace())
      .take(Double.parser())
  )
  .eraseToAnyParser()

/// Math expression parser that validates everything is consumed from input.
private let expression = additionAndSubtraction
  .skip(Whitespace())
  .take(End())
  .map { $0.0 }

final class ArithmeticTests: XCTestCase {

  func testAddition() {
    let eq = " 1  +     2+3    "
    let value: Double = 6
    XCTAssertEqual(value, expression.parse(eq))
  }

  func testSubtraction() {
    let eq = " 1  -     2 - 3    "
    let value: Double = -4
    XCTAssertEqual(value, expression.parse(eq))
  }

  func testOrderOfOperations() {
    let eq = " 1 + 2 * 3 / 4 - 5 ^ 2"
    let value: Double = 1 + 2 * 3 / 4 - pow(5, 2)
    XCTAssertEqual(value, expression.parse(eq))
  }

  func testParentheses() {
    let eq = " ( 1 + 2 ) * 3 / 4 - 5 ^ 2"
    let value: Double = ( 1 + 2 ) * 3 / 4 - pow(5, 2)
    XCTAssertEqual(value, expression.parse(eq))
  }

  func testNestedParentheses() {
    let eq = "((1 + 2) * (3 + 4)) / 5 ^ (1 + 3)"
    let value: Double = ((1 + 2) * (3 + 4)) / pow(5, 1 + 3)
    XCTAssertEqual(value, expression.parse(eq))
  }

  func testMissingClosingParenthesis() {
    let eq = "(1 + 2"
    let value: Double? = nil
    XCTAssertEqual(value, expression.parse(eq))
  }

  func testMissingOpeningParenthesis() {
    let eq = "1 + 2)"
    let value: Double? = nil
    XCTAssertEqual(value, expression.parse(eq))
  }
}