Leetcode基础刷题之PHP解析(150. Evaluate Reverse Polish Notation)

2019-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