PHP字符串运算结果,PHP 实现后缀表达式(接受四则运算字符串,输出计算结果,附代码)...
最近接觸了一個(gè)有趣的需求:給定變量a、b、c、d等若干,要求由用戶輸入的普通四則運(yùn)算字符串(包含加減乘除括號),算出具體的值。
例如,a=1,b=2,c=3,d=4,給出 a+b/(d-c),應(yīng)計(jì)算出結(jié)果為3,若為 a*b/(c-1) 則應(yīng)計(jì)算出結(jié)果為1
這種情況下,第一反應(yīng)可能是用數(shù)字值將字符串里的變量替換,然后通過eval()執(zhí)行。或者是將字符串中的每一項(xiàng)通過正則一個(gè)一個(gè)扣出來再進(jìn)行計(jì)算。
但這樣的邏輯太粗暴,代碼也太丑陋,其實(shí)大可不必如此。 此時(shí),讓我們將目光移向美麗的數(shù)據(jù)結(jié)構(gòu)與算法。
首先,我們了解一下 后綴表達(dá)式。
表達(dá)式一般由操作數(shù)(Operand)、運(yùn)算符(Operator)組成,例如算術(shù)表達(dá)式中,通常把運(yùn)算符放在兩個(gè)操作數(shù)的中間,
這稱為中綴表達(dá)式(Infix Expression),如A+B。我們?nèi)粘I钪惺褂玫木褪谴朔N方式
波蘭數(shù)學(xué)家Jan Lukasiewicz提出了另一種數(shù)學(xué)表示法,它有兩種表示形式:
把運(yùn)算符寫在操作數(shù)之前,稱為波蘭表達(dá)式(Polish Expression)或前綴表達(dá)式(Prefix Expression),如+AB;
把運(yùn)算符寫在操作數(shù)之后,稱為逆波蘭表達(dá)式(Reverse Polish Expression)或后綴表達(dá)式(Suffix Expression),如AB+
我們今天要探討的就是后綴表達(dá)式
我們?nèi)绾问褂盟?#xff1f;
首先我們要將平時(shí)用的中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式。
在此之前,我們需要一種常見的數(shù)據(jù)結(jié)構(gòu):棧,在這一步,我們需要兩個(gè)棧,操作數(shù)棧、運(yùn)算符棧
1、從左至右掃描一中綴表達(dá)式。
2、若讀取的是操作數(shù),則判斷該操作數(shù)的類型,并將該操作數(shù)存入操作數(shù)棧
3、若讀取的是運(yùn)算符
(1) 該運(yùn)算符為左括號”(“,則直接存入運(yùn)算符棧。
(2) 該運(yùn)算符為右括號”)”,則輸出運(yùn)算符棧中的運(yùn)算符到操作數(shù)棧,直到遇到左括號為止。
(3) 該運(yùn)算符為非括號運(yùn)算符:
(a) 若比運(yùn)算符棧棧頂?shù)倪\(yùn)算符優(yōu)先級高或相等,則直接存入運(yùn)算符棧。
(b) 若比運(yùn)算符棧棧頂?shù)倪\(yùn)算符優(yōu)先級低,則輸出棧頂運(yùn)算符到操作數(shù)棧,并將當(dāng)前運(yùn)算符壓入運(yùn)算符棧。
4、當(dāng)表達(dá)式讀取完成后運(yùn)算符棧中尚有運(yùn)算符時(shí),則依序取出運(yùn)算符到操作數(shù)棧,直到運(yùn)算符棧為空。
此時(shí),將操作數(shù)棧轉(zhuǎn)為一個(gè)字符串,它就是由我們輸入的中綴表達(dá)式轉(zhuǎn)化而來的后綴表達(dá)式
那么后綴表達(dá)式如何進(jìn)行計(jì)算呢?
1、從左到右掃描后綴表達(dá)式。
2、如果掃描的項(xiàng)目是操作數(shù),則將其壓入操作數(shù)棧,并掃描下一個(gè)項(xiàng)目。
3、如果掃描的項(xiàng)目是一個(gè)二元運(yùn)算符,則對棧的頂上兩個(gè)操作數(shù)執(zhí)行該運(yùn)算。
4、如果掃描的項(xiàng)目是一個(gè)一元運(yùn)算符,則對棧的最頂上操作數(shù)執(zhí)行該運(yùn)算。
5、將運(yùn)算結(jié)果重新壓入棧。
6、重復(fù)步驟2-5,直到后綴表達(dá)式掃描完畢,棧中即為結(jié)果值。
Talk is cheap,let me show you the code
接下來是使用PHP編寫的這樣一個(gè)工具類。可以接受傳入一個(gè)表達(dá)式和表達(dá)式各項(xiàng)對應(yīng)值 的數(shù)組,給出計(jì)算之后的結(jié)果。
使用方式:
RPNotation::calculate($exp, $exp_values);
例如:
$exp = "a+b-(c*d)/e";
$exp_values = ["a" => 1, "b" => 2, "c" => 3, "d" => 2, "e" => 3];
RPNotation::calculate($exp, $exp_values);
結(jié)果會是1
代碼內(nèi)容 :
1, '-' => 1, '*' => 2, '/' => 2, "(" => 0, ")" => 0];
/*
params:
$exp-普通表達(dá)式,例如 a+b*(c+d)
$exp_values-表達(dá)式對應(yīng)數(shù)據(jù)內(nèi)容,例如 ['a' => 1, 'b' => 2, 'c' => 3, 'd' => 4]
*/
public static function calculate($exp, $exp_values) {
$exp_arr = self::parse_exp($exp);//將表達(dá)式字符串解析為列表
if (!is_array($exp_arr)) {
return NULL;
}
$output_queue = self::nifix2rpn($exp_arr);
return self::calculate_value($output_queue, $exp_values);
}
//將字符串中每個(gè)操作項(xiàng)和預(yù)算符都解析出來
protected static function parse_exp($exp) {
$match = [];
preg_match_all(self::PATTERN_EXP, $exp, $match);
if ($match) {
return $match[0];
}else {
return NULL;
}
}
//將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式
protected static function nifix2rpn($input_queue){
$exp_stack = [];
$output_queue = [];
foreach($input_queue as $input) {
if (in_array($input, array_keys(self::EXP_PRIORITIES))){
if ($input == "(") {
array_push($exp_stack, $input);
continue;
}
if ($input == ")") {
$tmp_exp = array_pop($exp_stack);
while ($tmp_exp && $tmp_exp != "(") {
array_push($output_queue, $tmp_exp);
$tmp_exp = array_pop($exp_stack);
}
continue;
}
foreach(array_reverse($exp_stack) as $exp) {
if (self::EXP_PRIORITIES[$input] <= self::EXP_PRIORITIES[$exp]) {
array_pop($exp_stack);
array_push($output_queue, $exp);
}else {
break;
}
}
array_push($exp_stack ,$input);
}else {
array_push($output_queue, $input);
}
}
foreach(array_reverse($exp_stack) as $exp) {
array_push($output_queue, $exp);
}
return $output_queue;
}
//傳入后綴表達(dá)式隊(duì)列、各項(xiàng)對應(yīng)值的數(shù)組,計(jì)算出結(jié)果
protected static function calculate_value($output_queue, $exp_values) {
$res_stack = [];
foreach($output_queue as $out) {
if (in_array($out, array_keys(self::EXP_PRIORITIES))) {
$a = array_pop($res_stack);
$b = array_pop($res_stack);
switch ($out) {
case '+':
$res = $b + $a;
break;
case '-':
$res = $b - $a;
break;
case '*':
$res = $b * $a;
break;
case '/':
$res = $b / $a;
break;
}
array_push($res_stack, $res);
}else {
if (is_numeric($out)) {
array_push($res_stack, intval($out));
}else {
array_push($res_stack, $exp_values[$out]);
}
}
}
return count($res_stack) == 1 ? $res_stack[0] : NULL;
}
}
總結(jié)
以上是生活随笔為你收集整理的PHP字符串运算结果,PHP 实现后缀表达式(接受四则运算字符串,输出计算结果,附代码)...的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: java垃圾回收 分代_Java分代垃圾
- 下一篇: 如何转obj_Java 开发中如何正确的