Click here to Skip to main content
15,867,835 members
Articles / Programming Languages / XML

A “Natural” Expression Evaluator

Rate me:
Please Sign up or sign in to vote.
5.00/5 (5 votes)
21 Dec 2022CPOL3 min read 9.8K   157   19   10
Natural approach to calculate value of an expression
This article shows a different and more “natural” approach to the problem of calculating the value of an expression.

Introduction

I have always been bothered by the counter-intuitiveness of AST or RPN algorithm used to evaluate expressions. In this article, I will show a different and more “natural” approach to the problem of calculating the value of an expression.

The Idea

Let's say that I need to calculate this expression:

1+3*(5-(8-4)+(2+3)^2)

If I use pen and pencil to do the calculation, I would start reducing the expression by calculating the numerical result of the operations with the highest priorities and iteratively simplify the expression until I am left with the final numerical value:

Step 1 1+3*(5-4+5^2)
Step 2 1+3*(5-4+25)
Step 3 1+3*26
Step 4 1+78
Step 5 79

The expression evaluator that I coded follows exactly this idea, where the priority of an operation is calculated by combining the priority of the operator and its nesting level.

Operator Priority

Each arithmetical operator is assigned a base priority level.

Operator Priority
+ 1
- 1
* 2
/ 2
^ 3

If the operator is nested inside parentheses, the level of priority is equal to the base priority plus the nesting level multiplied by 10. The priority levels for the operators in the expression we just saw will look like this:

Image 1

By executing the operation starting from the highest level and replacing the operators and operand with the result, we can reduce the expression to a final value:

Image 2

Implementation

The implementation follows few steps:

  1. The input string containing the expression will be formatted.
  2. An array containing all the tokens of the expression will be built.
  3. A second array containing the levels of all the operators will be built.

Formatting

The formatting process will transform the input string in a string that follow certain rules. For example, the empty spaces will be eliminated, an expression like 2(3+1) will be transformed in 2*(3+1), etc. Also, it will throw an exception in case the input string starts with a operator different than plus or minus and other situations.

Tokenization

The tokenization process takes the formatted expression and produces:

  • an array containing the tokens (as shown above).
  • an array containing the priority for every operator.
  • an array containing the list of priority. This Array will be sorted and we will start the process of reduction from the highest value of priority.

Example

Let's suppose we have need to evaluate the expression string:

-5+2*(1+((7/8^2)-12^(-2))+9/4)

After being formatted, the string will be transformed into:

0-5+2*(1+((7/8^2)-12^(0-2))+9/4)

The tokenization process will create these three arrays:

_tokens

Image 3

_tokenPriority

Image 4

_priorityValues

Image 5

Again, let's recall how the calculation of the priority of an operator is done:

We start with the base priority of each operator:

+ -> 1

- -> 1

* -> 2

/ -> 2

^ -> 3

and to that, we add the level of parentheses the operator is in multiplied by 10.

Calculation

The array _priorityValues is sorted and starting from the highest value (in our example 33), all the operators in the _tokens array are calculated and then they are replaced with the result of that calculation. So the arrays _tokens and _tokensPriority get transformed from:

Image 6

to:

Image 7

and so on until we arrive at the final result.

Conclusion and Points of Interest

Clearly, the algorithm can be expanded and optimized in many different ways, but that is out of my scope for today. Attached to this article, there is a zipped Visual Studio project with all the code of the parser in a class and a simple Form.

Image 8

History

  • 21st December, 2022: Initial version

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Engineer
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionWonderful Pin
Maurice Marinus27-Feb-23 6:14
Maurice Marinus27-Feb-23 6:14 
QuestionAwsome Pin
Hossein Hosseini 202312-Jan-23 10:16
Hossein Hosseini 202312-Jan-23 10:16 
SuggestionNo need to have an evaluator Pin
Sergey Alexandrovich Kryukov26-Dec-22 18:17
mvaSergey Alexandrovich Kryukov26-Dec-22 18:17 
GeneralMy vote of 5 Pin
Hyland Computer Systems22-Dec-22 12:48
Hyland Computer Systems22-Dec-22 12:48 
GeneralThoughts Pin
PIEBALDconsult22-Dec-22 9:48
mvePIEBALDconsult22-Dec-22 9:48 
AnswerRe: Thoughts Pin
Sergey Alexandrovich Kryukov26-Dec-22 18:19
mvaSergey Alexandrovich Kryukov26-Dec-22 18:19 
QuestionI'm confused... Pin
Marc Clifton22-Dec-22 6:50
mvaMarc Clifton22-Dec-22 6:50 
In your example, the input is:

-5+2*(1+((7/8^2)-12^(-2))+9/4)

which gets transformed to:


0-5+2*(1+((7/8^2)-12^(0-2))+9/4)+(5+2)*(0-3+1)

Where does the bolded "+(5+2)*(0-3+1)" that's added after the "9/4)" come from?

AnswerRe: I'm confused... Pin
scastelli22-Dec-22 7:10
scastelli22-Dec-22 7:10 
PraiseAwesome Pin
Leigh Pointer22-Dec-22 3:07
professionalLeigh Pointer22-Dec-22 3:07 
PraiseExpression evaluation with variable priorities Pin
vit$oft22-Dec-22 0:14
vit$oft22-Dec-22 0:14 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.