Generating a Simple Algebraic Expression in Swift

Generating a simple algebraic expression in swift

Since all you want is a string representing an equation and a value for x, you don't need to do any solving. Just start with x and transform it until you have a nice equation. Here's a sample: (copy and paste it into a Playground to try it out)

import UIKit

enum Operation: String {
    case addition = "+"
    case subtraction = "-"
    case multiplication = "*"
    case division = "/"

    static func all() -> [Operation] {
        return [.addition, .subtraction, .multiplication, .division]
    }

    static func random() -> Operation {
        let all = Operation.all()
        let selection = Int(arc4random_uniform(UInt32(all.count)))
        return all[selection]
    }

}

func addNewTerm(formula: String, result: Int) -> (formula: String, result: Int) {
    // choose a random number and operation
    let operation = Operation.random()
    let number = chooseRandomNumberFor(operation: operation, on: result)
    // apply to the left side
    let newFormula = applyTermTo(formula: formula, number: number, operation: operation)
    // apply to the right side
    let newResult = applyTermTo(result: result, number: number, operation: operation)
    return (newFormula, newResult)
}

func applyTermTo(formula: String, number:Int, operation:Operation) -> String {
    return "\(formula) \(operation.rawValue) \(number)"
}

func applyTermTo(result: Int, number:Int, operation:Operation) -> Int {
    switch(operation) {
    case .addition: return result + number
    case .subtraction: return result - number
    case .multiplication: return result * number
    case .division: return result / number
    }
}

func chooseRandomNumberFor(operation: Operation, on number: Int) -> Int {
    switch(operation) {
    case .addition, .subtraction, .multiplication:
        return Int(arc4random_uniform(10) + 1)
    case .division:
        // add code here to find integer factors
        return 1
    }
}

func generateFormula(_ numTerms:Int = 1) -> (String, Int) {
    let x = Int(arc4random_uniform(10))
    var leftSide = "x"
    var result = x

    for i in 1...numTerms {
        (leftSide, result) = addNewTerm(formula: leftSide, result: result)
        if i < numTerms {
            leftSide = "(" + leftSide + ")"
        }
    }

    let formula = "\(leftSide) = \(result)"

    return (formula, x)
}

func printFormula(_ numTerms:Int = 1) {
    let (formula, x) = generateFormula(numTerms)
    print(formula, "                      x = ", x)
}

for i in 1...30 {
    printFormula(Int(arc4random_uniform(3)) + 1)
}

There are some things missing. The sqrt() function will have to be implemented separately. And for division to be useful, you'll have to add in a system to find factors (since you presumably want the results to be integers). Depending on what sort of output you want, there's a lot more work to do, but this should get you started.

Here's sample output:

(x + 10) - 5 = 11                       x =  6
((x + 6) + 6) - 1 = 20                       x =  9
x - 2 = 5                       x =  7
((x + 3) * 5) - 6 = 39                       x =  6
(x / 1) + 6 = 11                       x =  5
(x * 6) * 3 = 54                       x =  3
x * 9 = 54                       x =  6
((x / 1) - 6) + 8 = 11                       x =  9

Generating random doable math problems swift

I started programming with Turbo Pascal and as Niklaus Wirth said: Algorithms + Data Structure = Programs. You need to define data structures appropriate for your program.

First, some basic data structures. (Swift enum is much more powerful than that in other languages)

enum MathElement : CustomStringConvertible {
    case Integer(value: Int)
    case Percentage(value: Int)
    case Expression(expression: MathExpression)

    var description: String {
        switch self {
        case .Integer(let value): return "\(value)"
        case .Percentage(let percentage): return "\(percentage)%"
        case .Expression(let expr): return expr.description
        }
    }

    var nsExpressionFormatString : String {
        switch self {
        case .Integer(let value): return "\(value).0"
        case .Percentage(let percentage): return "\(Double(percentage) / 100)"
        case .Expression(let expr): return "(\(expr.description))"
        }
    }
}

enum MathOperator : String {
    case plus = "+"
    case minus = "-"
    case multiply = "*"
    case divide = "/"

    static func random() -> MathOperator {
        let allMathOperators: [MathOperator] = [.plus, .minus, .multiply, .divide]
        let index = Int(arc4random_uniform(UInt32(allMathOperators.count)))

        return allMathOperators[index]
    }
}

Now the main class:

class MathExpression : CustomStringConvertible {
    var lhs: MathElement
    var rhs: MathElement
    var `operator`: MathOperator

    init(lhs: MathElement, rhs: MathElement, operator: MathOperator) {
        self.lhs = lhs
        self.rhs = rhs
        self.operator = `operator`
    }

    var description: String {
        var leftString = ""
        var rightString = ""

        if case .Expression(_) = lhs {
            leftString = "(\(lhs))"
        } else {
            leftString = lhs.description
        }
        if case .Expression(_) = rhs {
            rightString = "(\(rhs))"
        } else {
            rightString = rhs.description
        }

        return "\(leftString) \(self.operator.rawValue) \(rightString)"
    }

    var result : Any? {
        let format = "\(lhs.nsExpressionFormatString) \(`operator`.rawValue) \(rhs.nsExpressionFormatString)"
        let expr = NSExpression(format: format)
        return expr.expressionValue(with: nil, context: nil)
    }

    static func random() -> MathExpression {
        let lhs = MathElement.Integer(value: Int(arc4random_uniform(10)))
        let rhs = MathElement.Integer(value: Int(arc4random_uniform(10)))

        return MathExpression(lhs: lhs, rhs: rhs, operator: .random())
    }
}

Usage:

let a = MathExpression(lhs: .Integer(value: 1), rhs: .Integer(value: 2), operator: .divide)
let b = MathExpression(lhs: .Integer(value: 10), rhs: .Percentage(value: 20), operator: .minus)
let c = MathExpression.random()

let d = MathExpression(lhs: .Integer(value: 1), rhs: .Integer(value: 2), operator: .plus)
let e = MathExpression(lhs: .Integer(value: 3), rhs: .Integer(value: 4), operator: .plus)
let f = MathExpression(lhs: .Expression(expression: d), rhs: .Expression(expression: e), operator: .multiply)

let x = MathExpression.random()
let y = MathExpression.random()
let z = MathExpression(lhs: .Expression(expression: x), rhs: .Expression(expression: y), operator: .plus)

print("a: \(a) = \(a.result!)")
print("b: \(b) = \(b.result!)")
print("c: \(c) = \(c.result!)")

print("f: \(f) = \(f.result!)") // the classic (1 + 2) * (3 + 4)
print("z: \(z) = \(z.result!)") // this is completely random

generating and executing all possible math equations

I'd think about this in terms of expression trees and context free grammars. You could say something like

EXPRESSION ::=
    1 | 2 | 3
  | ( EXPRESSION )+( EXPRESSION )
  | ( EXPRESSION )*( EXPRESSION )
  | ( EXPRESSION )^2
  | sqrt( EXPRESSION )
  ;

This is a bit over-eager on the parentheses, so if you care about beautiful strings you may want to clean up superfluous parens in a postprocessing step, or use some more elaborate grammar with multiple non-terminals to handle those correctly.

You can start with expression trees for the three terminal rules, i.e. your three constants. Then you can consider each of the recursive rules and plug the constants you have in place of the non-terminals. So you'd generate 1+1, 1+2, 1+3, 2+1, 2+2, 2+3, 3+1, 3+2, 3+3, (1)*(1), …. Something like

for op in [plus, times]:
  for lhs in expressions:
    for rhs in expressions:
      new_expressions.append(binaryop(lhs, op, rhs))
for op in [square, sqrt]:
  for arg in expressions:
    new_expressions.append(unaryop(op, arg))

Then after each such cycle, you would have to extend the set of expressions using the newly found ones. For the next round, you would try to ensure that at least one operand was generated in the last round. For binary operations, the other may have been older.

Perhaps things will become more feasible if you only use a single formula per possible value. So that once you have found that 1+3 can be used as an expression for 4, you don't do 2+2 and 2*2 and 2^2 and so on, as one way of expressing 4 is enough. Depends on the application.

Using Discriminating Union to implement basic Algebraic Simplification F#

I think the last line changed to

| Add(expr1, expr2) -> simplify(Add(simplify(expr1), simplify(expr2)))
//                     ^^^^^^^^^                                     ^

is the only change needed?

Equation (expression) parser with precedence?

The hard way

You want a recursive descent parser.

To get precedence you need to think recursively, for example, using your sample string,

1+11*5

to do this manually, you would have to read the 1, then see the plus and start a whole new recursive parse "session" starting with 11... and make sure to parse the 11 * 5 into its own factor, yielding a parse tree with 1 + (11 * 5).

This all feels so painful even to attempt to explain, especially with the added powerlessness of C. See, after parsing the 11, if the * was actually a + instead, you would have to abandon the attempt at making a term and instead parse the 11 itself as a factor. My head is already exploding. It's possible with the recursive decent strategy, but there is a better way...

The easy (right) way

If you use a GPL tool like Bison, you probably don't need to worry about licensing issues since the C code generated by bison is not covered by the GPL (IANAL but I'm pretty sure GPL tools don't force the GPL on generated code/binaries; for example Apple compiles code like say, Aperture with GCC and they sell it without having to GPL said code).

Download Bison (or something equivalent, ANTLR, etc.).

There is usually some sample code that you can just run bison on and get your desired C code that demonstrates this four function calculator:

http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html

Look at the generated code, and see that this is not as easy as it sounds. Also, the advantages of using a tool like Bison are 1) you learn something (especially if you read the Dragon book and learn about grammars), 2) you avoid NIH trying to reinvent the wheel. With a real parser-generator tool, you actually have a hope at scaling up later, showing other people you know that parsers are the domain of parsing tools.

---

Update:

People here have offered much sound advice. My only warning against skipping the parsing tools or just using the Shunting Yard algorithm or a hand rolled recursive decent parser is that little toy languages¹ may someday turn into big actual languages with functions (sin, cos, log) and variables, conditions and for loops.

Flex/Bison may very well be overkill for a small, simple interpreter, but a one off parser+evaluator may cause trouble down the line when changes need to be made or features need to be added. Your situation will vary and you will need to use your judgement; just don't punish other people for your sins ^[2] and build a less than adequate tool.

My favorite tool for parsing

The best tool in the world for the job is the Parsec library (for recursive decent parsers) which comes with the programming language Haskell. It looks a lot like BNF, or like some specialized tool or domain specific language for parsing (sample code [3]), but it is in fact just a regular library in Haskell, meaning that it compiles in the same build step as the rest of your Haskell code, and you can write arbitrary Haskell code and call that within your parser, and you can mix and match other libraries all in the same code. (Embedding a parsing language like this in a language other than Haskell results in loads of syntactic cruft, by the way. I did this in C# and it works quite well but it is not so pretty and succinct.)

Notes:

1 Richard Stallman says, in Why you should not use Tcl

The principal lesson of Emacs is that
a language for extensions should not
be a mere "extension language". It
should be a real programming language,
designed for writing and maintaining
substantial programs. Because people
will want to do that!

[2] Yes, I am forever scarred from using that "language".

Also note that when I submitted this entry, the preview was correct, but SO's less than adequate parser ate my close anchor tag on the first paragraph, proving that parsers are not something to be trifled with because if you use regexes and one off hacks you will probably get something subtle and small wrong.

[3] Snippet of a Haskell parser using Parsec: a four function calculator extended with exponents, parentheses, whitespace for multiplication, and constants (like pi and e).

aexpr   =   expr `chainl1` toOp
expr    =   optChainl1 term addop (toScalar 0)
term    =   factor `chainl1` mulop
factor  =   sexpr  `chainr1` powop
sexpr   =   parens aexpr
        <|> scalar
        <|> ident

powop   =   sym "^" >>= return . (B Pow)
        <|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))

toOp    =   sym "->" >>= return . (B To)

mulop   =   sym "*" >>= return . (B Mul)
        <|> sym "/" >>= return . (B Div)
        <|> sym "%" >>= return . (B Mod)
        <|>             return . (B Mul)

addop   =   sym "+" >>= return . (B Add) 
        <|> sym "-" >>= return . (B Sub)

scalar = number >>= return . toScalar

ident  = literal >>= return . Lit

parens p = do
             lparen
             result <- p
             rparen
             return result

Anyone know any good math equation wysiwyg's for actually letting users submit mathematical answers?

TinyMCE has always been a tried and true solution, and is compatible with MathJAX.

How to parse mathematical expressions involving parentheses

Ages ago when working on a simple graphing app, I used this algorithm (which is reasonably easy to understand and works great for simple math expressions like these) to first turn the expression into RPN and then calculated the result. RPN was nice and fast to execute for different variable values.

Of course, language parsing is a very wide topic and there are many other ways of going about it (and pre-made tools for it too)

iPhone iOS is there an expression parser for an algebraic calculator-like app?

A couple of open source options:

GCMathParser
http://www.apptree.net/parser.htm

DDMathParser
https://github.com/davedelong/DDMathParser

---

Related Topics