Home > Articles, Compilers & Interpreters > Implementation of algorithm for the calculating of prefix expressions.

Implementation of algorithm for the calculating of prefix expressions.

To calculate a prefix expression, we either convert a number from ASCII to decimal (in the loop ‘while’ at the end of the program) or implement the operation indicated by the first character of the expressions to the two terms, with a recursive calculation. This function is recursive, but it uses a global array containing the expression and an index number for the current character of the expression. The index number goes beyond each sub-expression calculated.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

char *expression = "+ * 4 5 6"; int i = 0;

int
eval () {
  int x = 0;

  while (expression[i] == ' ') i++;

  if (expression[i] == '+') {
    i++; return eval () + eval ();
  }

  if (expression[i] == '*') {
    i++; return eval () * eval ();
  }

  while ((expression[i] >= '0') && (expression[i] <= '9'))
    x = 10 * x + (expression[i++] - '0');

  return x;
}
  1. April 2, 2011 at 13:55

    All is well! 🙂

  2. April 2, 2011 at 11:50

    My mistake. I guess I read the wrong code about the wrong article 😛

    Sorry for the noise 😛

  3. April 2, 2011 at 00:54

    Before reaching any conclusions about whether I understand the recursion or not, you’d better study the article better. Try the code in a C++ program to determine whether it is right or not. The program works exactly as it should and it does what it is meant to. It is quite simple and only supports two binary operators (addition, multiplication). If you care about something more complete, you can see a complete calculator that I have developed in the following address: https://efxa.org/arduino_infix_calculator/. Also, if you are interested in something more sophisticated, you can study the interpreter that I have developed for the programming language YAFL: https://efxa.org/yafl-project/.

    But thank you for your interest 🙂

  4. April 1, 2011 at 17:57

    Sorry, but this code is wrong. Please do not use it in a real program 🙂

    I do not think you understand how recursion works…

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: