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;
}