Leetcode基礎刷題之PHP解析(150. Evaluate Reverse Polish Notation)
2 0 1 9 - 4 -10 星 期三 開 始 吧
上 一 題 鏈 接 Leetcode基礎刷題之PHP解析(225. Implement Stack using Queues)
題 目 描 述
這一題叫反向波蘭表示法.如果感興趣的話可以觀看維基百科對它的介紹: Reverse Polish notation .大概就是把運算元放在前面,操作符放在後面,有一定的規律就是,在操作符出現的時候,他的前面必然有兩個運算元(不然就沒法操作了),兩個運算元完成計算的同時,從陣列中刪除這兩個數,並且把新的值重新放回去.
題 目 分 析
第一時間想到就是堆疊的使用場景.每次取出陣列中的一個元素,判斷型別,如果,是數字的話,那麼就直接壓入棧當中,如果是操作符的話,那麼直接是從棧中彈出兩個元素進行計算,這裡要注意的是,在彈出的兩個元素當中,是元素A操作B,還是B操作A,看看上面的例子你就明白了.
/** * @param String[] $tokens * @return Integer */ function evalRPN($tokens) { $data=[]; $type=['+','-','*','/']; for($i=0;$i<count($tokens);$i++) { if(!in_array($tokens[$i],$type)) { array_unshift($data,intval($tokens[$i])); }else{ $val1=array_shift($data); $val2=array_shift($data); switch($tokens[$i]) { case '+': array_unshift($data,$val2+$val1); break; case '-': array_unshift($data,$val2-$val1); break; case '*': array_unshift($data,$val2*$val1); break; case '/': array_unshift($data,intval($val2/$val1)); break; default: } } } return current($data); }
開始在github慢慢整理自己學習資料結構和算題的筆記,明年的這個時候應該有點規模了吧. : https://github.com/wuqinqiang/leetcode-php