1

For example if I have I = V / R as input, I want V = I * R and R = V / I as output. I get it can be a broad question but how should I get started with it? Should I use stack/tree as when building postfix notation/interpreter?

Suresh Subedi
  • 660
  • 2
  • 10
  • 25
  • 2
    Expressions like that are a kind of tree, with associated permissible transformations corresponding to algebraic facts like "you can add the same number to both sides". So you'd have to start by parsing the expression into a tree, then generate the transforms. – Carlos Aug 09 '20 at 20:30

1 Answers1

1

You need to be able to represent the formulas symbolically, and apply algebraic rules to manipulate those formulas.

The easiest way to do this is to define a syntax that will accept your formula; best if defined explicitly as BNF. With that you can build a parser for such formulas; done appropriately your parser can build an abstract syntax tree representing the formula. You can do with tools like lex and yacc or ANTLR. Here's my advice on how do this with a custom recursive descent parser: Is there an alternative for flex/bison that is usable on 8-bit embedded systems?.

Once you have trees encoding your formulas, you can implement procedures to modify the trees according to algebraic laws, such as:

 X=Y/Z => X*Z = Y if Z ~= 0

Now you can implement such a rule by writing procedural code that climbs over the tree, finds a match to pattern, and then smashes the tree to produce the result. This is pretty straightforward compiler technology. If you are enthusiastic, you can probably code a half dozen algebraic laws fairly quickly. You'll discover the code that does this is pretty grotty, what with climbing up and down the tree, matching node, and smashing links between nodes to produce the result.

Another way to do this is to use a program transformation system that will let you

  • define a grammar for your formulas directly,
  • define (tree) rewrite rules directly in terms of your grammar (e.g., essentially you provide the algebra rule above directly),
  • apply the rewrite rules on demand for you
  • regenerate the symbolic formula from the AST

My company's DMS Software Reengineering Toolkit can do this. You can see a fully worked example (too large to copy here) of algebra and calculus at Algebra Defined By Transformation Rules

Ira Baxter
  • 93,541
  • 22
  • 172
  • 341