yaspr / polexpr Goto Github PK

This code takes an arithmetic expression and turns it into RPN using a tree built from two stacks.
The first stack is for operations (+, -, *, /, %, ^), the second is for operands.

Suppose the following expression: 2 * 34 / 4

1) push_operand(2);
2) push_operation(*);
3) push_operand(34);
4) compare priority of / and priority of top of the stack (*)
          / and * are of equal priority therfore
	  pop_operation(*);
	  pop_operand(34);
	  pop_operand(2);
	  push_operand(2 * 34);  --> This implies linking the tree nodes to their leaves: * is the node, 2 is the left leaf, 34 the right left
	  push_operation(/);

5) push_operand(4)

Empty stacks:
      while (pop_operation(op))  --> while there are still unprocessed operations
        {
	   pop_operand(b);
	   pop_operand(a);
	   push_operand(a op b);
	}

pop_operand(tree_root);


   tree_root  -->     /
                    /   \ 
                   *     4
		 /   \
		2     34

This code is simply a proof of concept, it handles strings as variables.
Parentheses are checked and spacing is allowed everywhere.

Some test expressions: (keep the quotes when spacing)

"(13 - 418) * x / y^2"
"2^2^2^2^2^(i^2 - 2*x)"

TODO:

   . parentheses location
   . add syntactic support for functions, a hash table for variables and another one for functions
   . add real values to numbers
   . add expression value evaluation (i.e. with x = 2: 2* x - 3 = 1)
   . make a symbolic computation command line interface


Compilation:

# cd src
# make
# make test E='"(13 - 418) * x / y^2"'
# make test E='"2^2^2^2^2^(i^2 - 2*x)"'

The binary file is in bin.