If you're new here, you may want to subscribe to my RSS feed. Thanks for visiting!

My last post about back to basics covered reverse polish notation including a link to a RPN parser which I wrote to allow people to learn by example (best way in my opinion and in yours). The post got quite long and the PHP code was not really relevant to the subject so I have decided to include in this separate post instead.

Here is how you parse RPN in Psuedo Code.

• While there are input tokens left
  • Read the next token from input.
  • If the token is a value
    • Push it onto the stack.
  • Otherwise, the token is a function. (Operators, like +, are simply functions taking two arguments.)
    • It is known that the function takes n arguments.
    • So, pop the top n values from the stack.
      • If there are fewer than n values on the stack
        • (Error) The user has not input sufficient values in the expression.
    • Evaluate the function, with the values as arguments.
    • Push the returned results, if any, back onto the stack.
• If there is only one value in the stack
  • That value is the result of the calculation.
• If there are more values in the stack
  • (Error) The user input too many values.

And then the PHP version.

$program = array()
 
$stack = array();
 
foreach($program as $token) {
	if(is_numeric($token)) {
		array_push($stack,$token);
	} else {
		if(count($stack) < 2) {
			// error
		}			
		$value1 = array_pop($stack);
		$value2 = array_pop($stack);
		switch($token) {
			case '+':
				array_push($stack,$value2 + $value1);
				break;
			case '-':
				array_push($stack,$value2 - $value1);
				break;
			case '*':
				array_push($stack,$value2 * $value1);
				break;
			case '/':
				array_push($stack,$value2 / $value1);
				break;
			default:
				// error
				break;
		}
	}
}
if(count($stack) == 1) {
	$result = array_pop($stack);
} else {
	$result = false;
}

Just a simple bit of code, the full version includes a lot of formatting code (check out the full application) and was thrown together so I doubt I will share it unless someone has a real need for it.

I will be looking (if time permits) to write the code to translate Infix TO Postfix and the reverse. Why? because it would be a useful tool to further teach programmers about the differences. So if anyone has any time or knows of any open source code that already does this then get in touch.