Expression parsing algorithm

Contents:

1. The basic idea
2. Using right associative operators
3. Using the open and close brackets
4. Using functions like sin() and cos()
5. Using the negative and factorial operators
6. Using the comparison and logical operators
7. Analysis of performance and correctness
8. Example implementation of the algorithm
9. Parsing while evaluating with stack based algorithm
10. Example implementation of stack based algorithm
11. Links
12. See also

The basic idea

1. Get the first item and initialise the tree with it.
2. Currently the root node is also the current node. The current node is the node we currently lie on.
3. Get the next item. This will be called the new item.
   
   
4. Climb up the tree as long as the precedence of the current node item is greater than or equal to that of the new item. When this is over, the current node item has a precedence strictly less than that of the new item.
   
   
5. Create a new node for the new item. Then set the left child of the new node to be the old right child of the current node. Finally set the new right child of the current node to be the new node (also set the parent of the new node).
   
   
6. Set the current node to be the new node.
7. Repeat steps 3, 4, 5 and 6 till there is no item left.

• operator plus + with precedence 2
• operator minus - with precedence 2
• operator times * with precedence 4
• operator divide / with precedence 4

Using right associative operators

• Step 4: Climb up the tree as long as the precedence of the current node item is strictly greater than that of the new item. When this is over, the current node item has a precedence less than or equal to that of the new item.

Using the open and close brackets

• Step 5: Set the new right child of the parent node to be the old right child of the current node, then delete the current node.
• Step 6: Set the current node to be the parent node.

Using functions like sin() and cos()

Using the negative and factorial operators

• operators ( and ) with precedence 1
• operator plus + with precedence 2
• operator minus - with precedence 2
• operator negative - with precedence 3
• operator times * with precedence 4
• operator divide / with precedence 4
• operator exponent ^ with precedence 5
• operator factorial ! with precedence 6

Using the comparison and logical operators

• operator or with precedence 1.2
• operator and with precedence 1.4
• operator not with precedence 1.6

Analysis of performance and correctness

1. On step 5 where the node is created and set.
2. On step 4 when the node is passed by another climbing up.

Example implementation of the algorithm

/*
	To compile with GCC, execute:
	gcc -Wall -ansi -pedantic -o calc expression-parsing-algorithm.c -lm

	To run, execute: ./calc 1+1 5-6/2+3*4
*/
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <math.h>

void* parse_expression (const char* expression);
double evaluate_expression_tree (const void* tree);
void print_expression_tree (const void* tree);
void delete_expression_tree (void* tree);

int main (int argc, char** argv)
{
	void* tree;
	double result;
	int i;
	if(argc<=1) printf("Usage: <program> <expression1> <expression2> ...\n");

	for(i=1; i<argc; i++)
	{
		printf("________________________________%d_\n", i);
		tree = parse_expression(argv[i]);
		if(tree==NULL) continue;

		print_expression_tree(tree);
		result = evaluate_expression_tree(tree);
		delete_expression_tree(tree);

		printf("result = %f\n", result);
	}
	return 0;
}

/* ... rest of source code ... */

typedef struct _Node {
	enum NodeID ID;
	int pre; /* precedence */
	double number;
	struct _Node *left, *right, *parent;
} Node;

Node* insert_node_item (Node* current, Node item, enum NodeInfo info)
{
	Node* node;

	if(info != SkipClimbUp)
	{
		/* step 4: climb up */
		if(info != RightAssociative)
		{
			/* for left-associative */
			while(current->pre >= item.pre)
				current = current->parent;
		}
		else
		{
			/* for right-associative */
			while(current->pre > item.pre)
				current = current->parent;
		}
	}

	if(item.ID == CLOSEBRACKET)
	{
		/* step 5.1: remove the '(' node */
		node = current->parent;
		node->right = current->right;
		if(current->right) current->right->parent = node;

		/* step 5.2: delete the '(' node */
		memset(current, 0, sizeof(Node));
		free(current);

		/* step 6: Set the 'current node' to be the parent node */
		current = node;
	}
	else
	{
		/* step 5.1: create the new node */
		node = malloc(sizeof(Node));
		*node = item;
		node->right = NULL;

		/* step 5.2: add the new node */
		node->left = current->right;
		if(current->right) current->right->parent = node;
		current->right = node;
		node->parent = current;

		/* step 6: Set the 'current node' to be the new node */
		current = node;
	}
	return current;
}

Parsing while evaluating with stack based algorithm

Example implementation of stack based algorithm

/*
	To compile with GCC, execute:
	gcc -Wall -ansi -pedantic -o calc expression-parse-and-evaluate.c -lm

	To run, execute: ./calc 1+1 5-6/2+3*4
*/
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <math.h>

double parse_and_evaluate_expression (const char* expression);

int main (int argc, char** argv)
{
	double result;
	int i;
	if(argc<=1) printf("Usage: <program> <expression1> <expression2> ...\n");

	for(i=1; i<argc; i++)
	{
		printf("________________________________%d_\n", i);
		result = parse_and_evaluate_expression(argv[i]);
		printf("result = %f\n", result);
	}
	return 0;
}

/* ... rest of source code ... */

typedef struct _Node {
	enum NodeID ID;
	int pre; /* precedence */
	double number;
} Node;

Node* insert_node_item (Node* current, Node item, enum NodeInfo info)
{
	double left, right;
	if(info == SkipClimbUp) current+=1;
	else
	{
		while(1)
		{
			if(info == RightAssociative)
			     { if(current->pre <= item.pre) break; }
			else { if(current->pre <  item.pre) break; }

			left  = (current-1)->number;
			right = (current+1)->number;
			switch(current->ID)
			{
			case POSITIVE:  (  current)->number = +right; break;
			case NEGATIVE:  (  current)->number = -right; break;
			case PLUS:      (--current)->number = left + right; break;
			case MINUS:     (--current)->number = left - right; break;
			case TIMES:     (--current)->number = left * right; break;
			case DIVIDE:    (--current)->number = left / right; break;
			case EXPONENT:  (--current)->number = pow(left, right); break;
			case FACTORIAL: (--current)->number = factorial(left); break;
			case SIN:       (  current)->number = sin(right); break;
			case COS:       (  current)->number = cos(right); break;
			case TAN:       (  current)->number = tan(right); break;
			default:        break;
			}
			current->ID = NUMBER; /* force node to be a number */
			current->pre = 10;    /* set to highest precedence */
			current--;  /* prepare for next iteration */
		}
		switch(item.ID)
		{
			case CLOSEBRACKET:
				*current = *(current+1);
				/* current-=1; this part is optional */
				break;
			case PLUS:
			case MINUS:
			case TIMES:
			case DIVIDE:
			case EXPONENT:
			case FACTORIAL: current+=2; break;
			default:        current+=1; break;
		}
	}
	if(item.ID != CLOSEBRACKET)
		*current = item;
	return current;
}

Links

1. http://en.wikipedia.org/wiki/Binary_expression_tree
2. https://en.wikipedia.org/wiki/Tree_traversal
3. https://en.wikipedia.org/wiki/Infix_notation
4. https://en.wikipedia.org/wiki/Time_complexity#Linear_time
5. http://en.wikipedia.org/wiki/Operator-precedence_parser
6. https://github.com/rhyscitlema/librfet

See also

• Evaluate any math expression online
• Convert sorted list to complete BST
• Generate nth palindromic number
• Find maximum bipartite matching