PHP スタックキュー

Contents

1. 中間記法、逆ポーランド記法
2. PHP スタックとキュー
3. スタック、逆ポーランド記法の計算
- 3.1. php
- 3.2. C の場合
4. 参照

中間記法、逆ポーランド記法

中間記法を逆ポーランド記法で入力して、それらを出力する。
中間記法は、(2+4)/(2-1)みたいな一般的な記述で、逆ポーランド記法は、24+21-/というような記述のこと。

PHP スタックとキュー

そもそもphpではスタック形式と通常の配列とで区別をしない。
array_push()（array_pop()で取り除く）でスタック形式で配列を作成できる。渡された変数は配列の最後に加えられる。なので、通常の$array[]=$a;のような形式と同じような意味を持つ。逆の意味を持つのは、array_unshift（array_shift）でこれらをキューと呼ぶ。

スタック、逆ポーランド記法の計算

入力を「1 2 + 3 4 -*」として「-3」を出力する。演算子は、+、-、*のみ。
（※途中で不明になった…。breakとか使わないと。）
⇒この辺り参照のこと（Cf,スタックとキューを極める！〜考え方と使い所を特集〜）

php

<?php
$input_line = trim(fgets(STDIN));
$string  = preg_replace("/( |　)/", "", $input_line );
$array = str_split ($string);
$stack = [];
foreach ($array as $key => $value){
    array_push($stack,$value);
}
$add = [];//+
$subtract = [];//-
$multiply = [];//*
foreach ($stack as $ke => $val){
    if($val == "+"){
        $add[] = $ke;
    }
    if($val == "-"){
        $subtract[] = $ke;
    }
    if($val == "*"){
        $multiply[] = $ke;
    }
}
$result =0;
$res = 0;
$res2 = 0;
foreach ($stack as $k => $v){
    if($k < $add[0]){
        $result += $stack[$k];
    }
    if($k < $subtract[0]){
        if(is_numeric($v) && ($add[0] < $k)){
            $res = $v;
        }
    }
    if($k < $multiply[0]){
        if(is_numeric($v) && ($subtract[0] < $k)){
            $res2 = $v;
        }else{
            
        }
    }
}
var_dump($res);
var_dump($res2);
?>

C の場合

一応、Cの場合で参照。

int main(){
  int a,b;
  top = 0;
  char s[100];

  while( scanf("%s", s) != EOF) {
    if( s[0] == '+' ) {
      a = pop();
      b = pop();
      push(a + b);
    } else if(s[0] == '-'){
      b = pop();
      a = pop();
      push(a - b);
    } else if(s[0] == '*'){
       a = pop();
       b = pop();
       push(a * b);
    } else{
       push(atoi(s))
    }
  }
  printf("%d\n",pop());
  return 0;
}