1

I'm currently working on a script interpreter for a game I'm porting as a personal project - I have asked a few questions in regard to it earlier.

It's starting to work pretty well, I did however came to the point where I have to evaluate boolean expressions, for example the ones in while-loops, if-statements, etcetera.

My current code tokenizes the script, and passes the boolean expression to a function called ProcessExpression(string[] tokens) when it encounters one. An example token-array could be:

local.i
<=
local.arrayLength
+
1
&&
(
local.i
<
local.notThis
||
local.i
>
local.notThis
)

Thinking about how to tackle the actual evaluation, I figured I'd start by replacing the variables with actual values, for example: local.i would become 0, local.arrayLength would become 16 and local.notThis would become 10.

Then I thought about pulling the resulting tokens through a postfix calculator to get rid of all the math, leaving just the logical conditions.

However, I'm kind of on the fence if this is the approach I should take or not. Seeing as the postfix calculation alone would add a lot code, I was wondering if there are some tricks I didn't think off? If postfix is indeed the way to go, can I somehow also make it handle the logical conditions alongside with the math operators?

I'm making this in C#, but I am however unwilling to use external libraries or some kind of "Eval"-function. I'm also not interested in making a grammar for this using things like ANTLR, as there must be less intrusive ways for something seemingly "simple" as an expression solver (if that would be the term for it).

Lennard Fonteijn
  • 2,561
  • 2
  • 24
  • 39
  • An "expression solver" is predicated on a syntax tree. A syntax tree is best derived from a string via a grammar. To not use a grammar is almost certainly not the wisest solution, except as a learning exercise for yourself. – Kirk Woll Oct 05 '13 at 00:17
  • @KirkWoll If you know of ways to implement simple grammars without me requiring to use libaries like ANTLR I'd be very willing to listen to the possibilities! – Lennard Fonteijn Oct 05 '13 at 00:20
  • Well, to consume a grammar, you need to either use a library, or you need to write that library yourself. I've used [Irony](http://irony.codeplex.com/) in the past to good effect, and it has the virtue that you don't have to step out of C# at all. (the grammars are defined in C# itself) – Kirk Woll Oct 05 '13 at 00:22
  • I was afraid you were going to say that, I had hoped I could solve the logical expressions in a similar fashion I could with math operators (postfix calculator), since it seems like I have to add that regardless of anything. Unless there are other ways to solve math expressions, I think I'm stuck with postfix as the most effective solution, no? – Lennard Fonteijn Oct 05 '13 at 00:24
  • not sure what your hangup is with using a library. You're already using the "library" known as the .NET framework. The problem domain of converting a string into programming constructs (expressions) is a solved problem. (and the solution, of course, is grammars/parsers, etc.) – Kirk Woll Oct 05 '13 at 00:27
  • I have a fixed list of math and logical operators, the math can be solved with a postfix, in worst case, I could solve the logical operators in a similar fashion. My question is about what other alternatives I have, if grammars is one such way, that's great, but I am hoping to find one which just doesn't have the library dependency. To answers your question: portability. The less libraries I use, the easier it will be to port this back to C++, which is my intention (all learning exercises, not practical). – Lennard Fonteijn Oct 05 '13 at 00:32
  • If I were to use a grammar, I'd probably write a lexer for the full scripting language, it's just not as "fun" :P – Lennard Fonteijn Oct 05 '13 at 00:34

1 Answers1

0

So, to answer my own question: I ended up using a postfix calculator approach.

I pass on all tokens to my ExpressionSolver class, this will convert it from Infix to Postfix and then evaluate the Postfix. The operator-list also contains the && and || operators and handles them accordingly when they are encountered.

I also ended up making a simple Regex-based lexer for tokenizing my input after what Kirk Woll said. It certainly made my parsing before I actually get to solving an expression much easier, I used the following resource for that (also see my comment there): Poor man's "lexer" for C#

Community
  • 1
  • 1
Lennard Fonteijn
  • 2,561
  • 2
  • 24
  • 39