Как найти ключ и вернуть его путь через иерархию в JSON, используя Perl

Question

{

  "root1" : {
      "sub1" : null,
      "sub2" : {
         "subsub1" : {
            "key1" : {

            },
            "key2" : {

            },
            "key3" : {

            },
            "key4" : {

            }
         }
      },
      "sub3" : {
         "subsub2" : {
            "key5" : {

            }
         }
      }
  },
  "root2" : {
      "sub1" : null,
      "sub2" : {
         "subsub1" : {
            "key1" : {

            },
            "key2" : {

            },
            "key3" : {

            },
            "key4" : {

            }
         }
      },
      "sub3" : {
         "subsub2" : {
            "key8" : {

            }
         }
      }
  }
}

рассмотрите вышеупомянутый JSON. Как узнать, существует ли «ключ8» в этом файле json, а также найти путь, по которому его нашли в файле json.

например, при поиске 'key8' необходимо получить вывод, похожий на:

root2->sub3->subsub2->key8

Answer 1

Это просто прямой обход дерева. Следующее возвращается, как только найдено совпадение (вместо поиска всех совпадений).

sub key_search {
    my $target = $_[1];   
    my @todo = [ $_[0] ];
    while (@todo) {
        my ($val, @path) = @{ shift(@todo) };
        my $reftype = ref($val);
        if (!$reftype) {
           # Nothing to do
        }
        elsif ($reftype eq 'HASH') {
           for my $key (keys(%$val)) {
              return @path, $target if $key eq $target;

              push @todo, [ $val->{$key}, @path, $key ];
           }
        }
        elsif ($reftype eq 'ARRAY') {
           for my $i (0..$#$val) {
              push @todo, [ $val->[$i], @path, $i ];
           }
        }
        else {
           die("Invalid data.\n");
        }
    }

    return;
}

my @path = key_search($data, 'key8')
   or die("Not found.\n");

Примечания * * 1004

• Результат будет неоднозначным, если данные могут содержать массивы и если любой из хэшей может иметь целые числа для ключей. Могут быть предприняты шаги для устранения их неоднозначности.
• Выше не проверяются циклы, но они не могут существовать в JSON.
• Замените push на unshift, чтобы получить поиск в глубину вместо поиска в ширину.