php逆波兰表达式,PHP根据数字的字符表达式计算出结果（转换成逆波兰式再求解）[转]...
這個簡單的計算器采用的是逆波蘭式來做的，僅支持加減乘除四種運算，純粹個人練習記錄一下，還望多多支持。
用法
require 'Calc.php';
$calc = new Calc('(1+9)/2');
echo $result = $calc->calculate();
將算術表達式轉換成逆波蘭式
1、建立運算符棧stackOperator用于運算符的存儲，壓入’@’；建立逆波蘭式存儲棧stackOut，并置空。
2、預處理表達式，正、負號前加0(如果一個加號(減號)出現在最前面或左括號后面，則該加號(減號)為正負號) 。
3、順序掃描表達式，如果當前字符是數字(優(yōu)先級為0的符號)，則直接入棧stackOut；如果當前字符為運算符或括號(優(yōu)先級不為0的符號)，則判斷第4點 。
4、若當前運算符為'(‘，直接入棧stackOperator；
若為’)’，出棧(stackOperator)并順序輸出運算符直到遇到第一個'(‘，遇到的第一個'(‘ 出棧(stackOperator)但不輸出；
若為四則運算符，比較棧頂元素與當前元素的優(yōu)先級：
如果棧頂元素運算符優(yōu)先級 >= 當前元素的優(yōu)先級， 出棧并順序輸出運算符直到棧頂元素優(yōu)先級當前元素的優(yōu)先級，直接入棧(stackOperator)。
5、重復第3點直到表達式掃描完畢。
6、順序出棧(stackOperator)并將輸出的元素壓入棧stackOut，直到棧頂元素為’@’。
計算逆波蘭式
1、準備一個棧stack，并置空。
2、順序讀取(從棧底到棧頂)棧stackOut，碰到操作數，入棧stack。
3、碰到操作符，stack彈出兩個元素，運算并將運算結果入棧stack。
4、重復執(zhí)行2~3步驟，棧stack即是表達式結果。
實現代碼
/**
* php簡單實現算術表達式轉換成逆波蘭式，并求解。
* 僅支持加減乘除四種運算
* @author joe, joenali@163.com
* @date 2013-01-17
*
* require 'Calc.php';
* $calc = new Calc('(1+9)/2');
* echo $calc->getExpression();
* echo $calc->calculate();
*
*/
class Calc {
protected $_stackOperator = array('@');
protected $_stackOut = array();
protected $_operator = array('@', '(', ')', '+', '-', '*', '/');
protected $_priority = array('@' => 0, '(' => 10, ')' => 10, '+' => 20, '-' => 20, '*' => 30, '/' => 30);
public function __construct($expression) {
$this->convert($expression);
}
/**
* 解析字符串表達式
* 解析字符串表達式，將數字和運算符分離，用數組存儲
* @param string $expression
* @return array
*/
protected function expressionParase($expression) {
$arr = str_split($expression);
$data = $tmp = array();
do {
$item = array_shift($arr);
if (in_array($item, $this->_operator)) {
if ($tmp) {
array_push($data, implode('', $tmp));
$tmp = array();
}
array_push($data, $item);
} else {
array_push($tmp, $item);
}
} while(count($arr));
array_push($data, implode('', $tmp));
return $data;
}
/**
* 生成逆波蘭式
* @param string $expression
*/
protected function convert($expression) {
foreach ($this->expressionParase($expression) as $char) {
if (preg_match("/^[0-9]+$/", $char)) {
array_push($this->_stackOut, $char);
} else if (in_array($char, $this->_operator)) {
if ('(' == $char) {
array_push($this->_stackOperator, $char);
} else if (')' == $char) {
while (count($this->_stackOperator) > 1) {
$drop = array_pop($this->_stackOperator);
if ('(' == $drop) {
break;
} else {
array_push($this->_stackOut, $drop);
}
}
} else {
while (count($this->_stackOperator)) {
$oTop = end($this->_stackOperator);
if ($this->_priority[$char] > $this->_priority[$oTop]) {
array_push($this->_stackOperator, $char);
break;
} else {
$drop = array_pop($this->_stackOperator);
array_push($this->_stackOut, $drop);
}
}
}
}
}
while (count($this->_stackOperator)) {
$drop = array_pop($this->_stackOperator);
if ('@' == $drop) {
break;
} else {
array_push($this->_stackOut, $drop);
}
}
}
/**
* 獲取逆波蘭式
* @return string
*/
public function getExpression() {
return implode('', $this->_stackOut);
}
/**
* 計算逆波蘭式
* @return int
*/
public function calculate() {
$stack = array();
foreach ($this->_stackOut as $char) {
if (preg_match("/^[0-9]+$/", $char)) {
array_push($stack, $char);
} else if (in_array($char, $this->_operator)) {
$b = array_pop($stack);
$a = array_pop($stack);
array_push($stack, $this->operator($a, $b, $char));
}
}
return end($stack);
}
protected function operator($a, $b, $o) {
switch ($o) {
case '+':
return intval($a) + intval($b);
break;
case '+':
return intval($a) + intval($b);
break;
case '-':
return intval($a) - intval($b);
break;
case '*':
return intval($a) * intval($b);
break;
case '/':
return intval($a) / intval($b);
break;
}
}
}
另一版：
$str = '1+1/2';
echo calc($str);
function calc($expression = ''){
$_stackOperator = array('@');
$_stackOut = array(); // 獲取逆波蘭式
$_operator = array('@', '(', ')', '+', '-', '*', '/');
$_priority = array('@' => 0, '(' => 10, ')' => 10, '+' => 20, '-' => 20, '*' => 30, '/' => 30);
// 分離運算符和數字
$arr = str_split($expression);
$data = $tmp = array();
do {
$item = array_shift($arr);
if (in_array($item, $_operator)) {
if ($tmp) {
array_push($data, implode('', $tmp));
$tmp = array();
}
array_push($data, $item);
} else {
array_push($tmp, $item);
}
} while(count($arr));
array_push($data, implode('', $tmp));
// 生成逆波蘭式
foreach ($data as $char) {
if (preg_match("/^[0-9]+$/", $char)) {
array_push($_stackOut, $char);
} else if (in_array($char, $_operator)) {
if ('(' == $char) {
array_push($_stackOperator, $char);
} else if (')' == $char) {
while (count($_stackOperator) > 1) {
$drop = array_pop($_stackOperator);
if ('(' == $drop) {
break;
} else {
array_push($_stackOut, $drop);
}
}
} else {
while (count($_stackOperator)) {
$oTop = end($_stackOperator);
if ($_priority[$char] > $_priority[$oTop]) {
array_push($_stackOperator, $char);
break;
} else {
$drop = array_pop($_stackOperator);
array_push($_stackOut, $drop);
}
}
}
}
}
while (count($_stackOperator)) {
$drop = array_pop($_stackOperator);
if ('@' == $drop) {
break;
} else {
array_push($_stackOut, $drop);
}
}
// 計算逆波蘭式
$stack = array();
foreach ($_stackOut as $char) {
if (preg_match("/^[0-9]+$/", $char)) {
array_push($stack, $char);
} else if (in_array($char, $_operator)) {
$b = array_pop($stack);
$a = array_pop($stack);
switch ($char) {
case '+':
array_push($stack, intval($a) + intval($b));
break;
case '+':
array_push($stack, intval($a) + intval($b));
break;
case '-':
array_push($stack, intval($a) - intval($b));
break;
case '*':
array_push($stack, intval($a) * intval($b));
break;
case '/':
array_push($stack, intval($a) / intval($b));
break;
}
}
}
return end($stack);
}
?>
轉自：http://my.oschina.net/u/566545/blog/103030
總結
以上是生活随笔為你收集整理的php逆波兰表达式,PHP根据数字的字符表达式计算出结果（转换成逆波兰式再求解）[转]...的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java常用注解及功能_SpringBo
- 下一篇： php输出多维json,json多维数组