Recursive Postfix Expression Evaluator

In a previous post (here). I created a Reverse Polish Notation calculator which would take digits in along with operators in postfix form and return an evaluated expression. The RPN calculator was implemented using my own Stack data structure (based off of an array). The following program is a postfix expression evaluator which uses recursion as a kind of stack implementation. As operands are found in the expression the eval function goes deeper into the recursion (recurses = push operands on stack). When a operator is found the eval function effectively moves up levels in the recursion (popping) values and performing the necessary operations. Enjoy:

/*

 *  

 *

 *  Created by Devin Eldreth on 11/2/07.

 * This program contains a recursive postfix expression evaluator (eval). A global array of characters is set to a postfix expression.

 * eval is called and recursively evaluates the expression to return the integer result. Current the function only works with single digit operands

 * and any of the four mathematical operators +, -, *, /

 */

#include

#include

char *a; // Define a string to hold the expression

int i = 0, y = 0, skip = 0; // Initilize 3 integer values. y will basically the top of the stack (recursively). 

    //Skip will be the test to see if we have already recursed twice and will increment i

int main(){

//a = "5 9 8 + 6 4 * * 7 + *"; //= 2075 (Problem in book)

//a = "2 6 / 8 *"; //= 24

a = "3 5 4 6 * * * 2 / 3 -"; //= 177

printf("\n%s = %d\n", a, eval());

return 0;

}

int eval(){

int x = 0;

for(;;){

while(a[i] == ' ') i++; // Always increment array index if it is just a space

// Return the calculated value y if there is an operator or assume termination when i is the value of the length of the array

// This will actually bring values back from the recursion

if((i == strlen(a)) || (a[i] == '*') || (a[i] == '+') || (a[i] == '-') || (a[i] == '/')) return y;

// Read each array element and recurse after getting the numberical value at index i

while((a[i] >= '0') && (a[i] <= '9')){

x = (a[i++] -'0');

eval();

}

if(a[i] == '*'){ // Handle the multiplicative operator

if(y == 0) y++;

y *= x; 

skip++; // Check to see if the y value is 0 and increment it to handle the initial multiplication. Increment skip.

}

if(a[i] == '+'){ // Handle the addition operator

y = (y == 0) ? x : y + x; 

skip++; // Test to see if y is 0 and set it to x (this isn't quite necessary). Increment skip.

}

if(a[i] == '-'){ // Handle the difference operator

y = (y == 0) ? x : y - x; 

skip++; // Identical to the addition handling test.

}

if(a[i] == '/'){ // Handle the division operator

y = (y == 0) ? x : y / x; 

skip++; // Identical to the addition test.

}

// Check to see if skip is equal to 2. Increment i and set skip equal to 1. This will handle the event that the counter becomes stuck on a single operator.

if(skip == 2) { i++; skip = 1; }

}

}