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

Created 5 years ago by 吴亲库里, Updated 5 years ago Revision #1 2558 views 0 likes 0 collects

2019-4-10 星期三开始吧

上一题链接 Leetcode基础刷题之PHP解析(225. Implement Stack using Queues)

题目描述

这一题叫反向波兰表示法.如果感兴趣的话可以观看维基百科对它的介绍:Reverse Polish notation.大概就是把操作数放在前面,操作符放在后面,有一定的规律就是,在操作符出现的时候,他的前面必然有两个操作数(不然就没法操作了),两个操作数完成计算的同时,从数组中删除这两个数,并且把新的值重新放回去.

题目分析

第一时间想到就是堆栈的使用场景.每次取出数组中的一个元素,判断类型,如果,是数字的话,那么就直接压入栈当中,如果是操作符的话,那么直接是从栈中弹出两个元素进行计算,这里要注意的是,在弹出的两个元素当中,是元素A操作B,还是B操作A,看看上面的例子你就明白了.

xxxxxxxxxx
 
/**
     * @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);
    }