Posted on by Kalkicode
Code Stack

Evaluate postfix expression using stack in php

Php program for Evaluate postfix expression using stack. Here problem description and explanation.

<?php
/* 
    Php program for 
    Evaluate postfix expression
*/
// Stack Node
class StackNode
{
	public $operand;
	public $next;
	public	function __construct($operand, $top)
	{
		$this->operand = $operand;
		$this->next = $top;
	}
}
class MyStack
{
	public $top;
	public $count;
	public	function __construct()
	{
		$this->top = NULL;
		$this->count = 0;
	}
	// Returns the number of element in stack
	public	function isSize()
	{
		return $this->count;
	}
	public	function isEmpty()
	{
		if ($this->isSize() > 0)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Add a new element in stack
	public	function push($value)
	{
		// Make a new stack node
		// And set as top
		$this->top = new StackNode($value, $this->top);
		// Increase node value
		$this->count++;
	}
	// Remove a top element 
	public	function pop()
	{
		$value = $this->peek();
		if ($this->isEmpty() == false)
		{
			$this->top = $this->top->next;
			// Reduce the size
			$this->count--;
		}
		return $value;
	}
	// Used to get top element of stack
	public	function peek()
	{
		if (!$this->isEmpty())
		{
			return $this->top->operand;
		}
		else
		{
			return 0;
		}
	}
}
class Execution
{
	public	function evaluate($e)
	{
		// Get the length of expression
		$size = strlen($e);
		$a = 0;
		$b = 0;
		$s = new MyStack();
		$isVaild = true;
		// work with (+,-,/,*,%) operator
		for ($i = 0; $i < $size && $isVaild; $i++)
		{
			if ($e[$i] >= '0' && $e[$i] <= '9')
			{
				$a = ord($e[$i]) - ord('0');
				$s->push($a);
			}
			else if ($s->isSize() > 1)
			{
				$a = $s->pop();
				$b = $s->pop();
				// Perform arithmetic operations between 2 operands
				if ($e[$i] == '+')
				{
					$s->push($b + $a);
				}
				else if ($e[$i] == '-')
				{
					$s->push($b - $a);
				}
				else if ($e[$i] == '*')
				{
					$s->push($b * $a);
				}
				else if ($e[$i] == '/')
				{
					$s->push((int)($b / $a));
				}
				else if ($e[$i] == '%')
				{
					$s->push($b % $a);
				}
				else
				{
					// When use other operator
					$isVaild = false;
				}
			}
			else if ($s->isSize() == 1)
			{
				// Special case  
				// When use +, - at the beginning
				if ($e[$i] == '-')
				{
					$a = $s->pop();
					$s->push(-$a);
				}
				else if ($e[$i] != '+')
				{
					// When not use  +,-
					$isVaild = false;
				}
			}
			else
			{
				$isVaild = false;
			}
		}
		if ($isVaild == false)
		{
			// Possible case use other operators
			// 1) When using special operators
			// 2) Or expression is invalid
			echo $e.
			" Invalid expression ", "\n";
			return;
		}
		echo $e.
		" = ".strval($s->pop()), "\n";
	}
	public static
	function main($args)
	{
		$task = new Execution();
		// Execute the following expression
		// (1+2)*(3+5)
		$task->evaluate("12+35+*");
		// -((7*2) + (6/2) + 4)
		$task->evaluate("72*62/+4+-");
	}
}
Execution::main(array());

Output

12+35+* = 24
72*62/+4+- = -21

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment