Jump to content
  • Advertisement
Sign in to follow this  
Mizipzor

Textbased math

This topic is 3795 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

x = a + 2 * b + 3 * c
The above is what I have. a, b and c are all variables, the signs work like you would expect. What would the best approach towards writing an algorithm that calculated x based on the string?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Mizipzor
x = a + 2 * b + 3 * c


The above is what I have. a, b and c are all variables, the signs work like you would expect.

What would the best approach towards writing an algorithm that calculated x based on the string?


What string? What types are a, b and c? It is just maths, you do it pretty much the same way as you would with pen and paper.

I don't think I understand your problem.

Share this post


Link to post
Share on other sites
Quote:
Original post by visage
Shunting Yard Algorithm to Reverse Polish Notation Algorithm?

Then use some sort of regular expression pattern matching to determine if an input is a variable and check your variable registry to see if it can be replaced. If it can, replace it. Otherwise, throw an error.


Yep, I certainly did not understand the question :). Thanks for the useful links though, at least I learnt something.

Share this post


Link to post
Share on other sites
lex, parse, tree rewrite (symbol substitution), and evaluate.

these steps can often be combined.

you do need the parse (a step above basic regex style lexing) to ensure correct handling of operator precedence.

if you want to hard code it then look at recursive decent parsing algorithms. you probably cannot avoid building a tree with this approach since you only want to have to do the symbol substitution once and evaluate once. recursive descent just exhaustively iteratates a set of rules until it finds a production match and so combining the parsing and substitution and evaluation would mean clobbering the symbol table unnecessarily.

generally its considered a good idea to factor out the grammar from the invariant parsing algorithm which leads naturally to grammar rules that are independent of the parsing algorithm.

there is a simple calculator example in the (gnu) bison (a c code parser generator) manual that could be adapated to deal with the symbol stuff and it would evaluate without having to do the extra lifting of building a tree.

an adapted example in ocaml using a parsing expression grammar (peg) module (linear parsing algorithm with infinite lookahead) - with simple symbol substution would like this. it combines the lex and parse stages and the substitution and evaluation stages.

open Aurochs_pack
open Peg

let _ =
let grammar ="
int ::= <num>val:[0-9]+</num>;
ident ::= <ident> name:[a-zA-Z]+ </ident>;
outfixing [ \\n\\t]* do
start ::= sum EOF;
sum ::= <add> term '+' sum </add> | term;
term ::= <mul> simple '*' term </mul> | simple;
simple ::= int | '(' sum ')' | ident;
done;"
in
let rec eval = function
| Node("root", _, [x]) -> eval x
| Node("add", _, [x;y]) -> (eval x) + (eval y)
| Node("mul", _, [x;y]) -> (eval x) * (eval y)
| Node("num", ["val",x], []) -> int_of_string x
(* in place of symbol lookup - identifiers just get substitued a value of 999 *)
| Node("ident", ["name",x], []) -> Printf.printf "subst 999 for %s\n" x ; 999
| _ -> assert false
in
while true do
Printf.printf "> %!";
let u = input_line stdin in
try
let t = Aurochs.see ~grammar:(`Source(`String grammar)) ~text:(`String u) in
let x = eval t in
Printf.printf "%d\n%!" x;
with
| x ->
Printf.printf "Exception: %s\n%!" (Printexc.to_string x)
done

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!