Calculating the value of the expression "on the knee"

The topic is inspired by recent posts Expression Compiler and Expression Value Calculation . Two approaches are considered - the construction of a semantic expression tree for quick calculation and the calculation of the expression itself on the move with the help of two of its stacks. I want to show a fairly simple way to implement, in fact, the algorithm from the first article, but on the basis of recursion. Sometimes it is appropriate to shift some of the work with the stack to the compiler, since modern OSs give us a big stack and the possibility of using recursion wisely.

So what is an arithmetic expression? As it was written in the first mentioned article, the structure of the expression can be defined by the following rules:

  expression :: = addend ["+" or "-" addend] *
 term :: = multiplier ["*" or "/" multiplier] *
 factor :: = number |  variable |  (expression) |  + multiplier |  -factor 

')
To the note: this form of grammar description is often used in technical documentation. In theory, it is called BNF, those who wish can read in more detail, for example, on Wikipedia .

The problem of analyzing text according to a certain formal grammar is usually solved in two ways: explicit construction of a finite state machine (about this later) and a simple recursive analysis, which we will now implement.

Guided by the above scheme, you can easily write the following code to analyze the first rule:

  calculate_expression ()
	 result = calculate term ()
	 while there are characters
		 if current_character = "+"
			 result = result + calculate term ()
		 or if current_character = "-"
			 Result = Result - Calculate_to ()
		 otherwise
			 mistake
	 return result 

The analysis of multiplication operations is written in an absolutely similar way, and at the lowest level of analysis we come to recursion - to calculate the value in brackets, we simply call to evaluate_expression ().

  calculate multiplier ()
	 result = 0
	 if current_character digit
		 result = read_number ()
	 or if current_character letter
		 result = calculate_variable ()
	 or if current_character = "("
		 result = calculate_expression ()
		 if the current character! = ")"
			 mistake
	 or if current_character = "+"
		 Result = Calculate_ Multiplier ()
	 or if current_character = "-"
		 result = -calculate_ multiplier ()
	 otherwise
		 mistake
	 return result 

Yes, in the given pseudocode, spaces are not taken into account, but this is enough for general introduction to the idea. Those who wish to familiarize themselves with the working implementation of such an approach in C ++ can suggest reading my code in the Popup Plus plugin for Miranda: formula.h and formula.cpp .

PS If there are people willing to read about how grammars and finite automata can be used to compile other texts, I can write about a simple XPath parser inside a Jabber module from the same Miranda. Or how to parse XML.