php - phpで中置する接頭辞

Question

PHPで中置に接頭辞を実装しようとしています。入力は、たとえば次のようになります。

prefix  * + 3 2 4
infix   ((3+2)*4)

(* + 3 2 4)PHPまたはJavaScriptを使用して、接頭辞式を中置式に変換したい(((3+2)*4))。

Answer 1

これは、プレフィックスからポストフィックスへの表記の基本的なアルゴリズムです（を使用stack）。

   IF stack is not empty
     a. Temp -->pop the stack
     b. IF temp is a operator
       i. Write a opening parenthesis to output
       ii. prefixToInfix(stack)
       iii. Write temp to output
       iv. prefixToInfix(stack)
       v. Write a closing parenthesis to output
    c. ELSE IF temp is a space -->prefixToInfix(stack)
    d. ELSE
       i. Write temp to output
       ii. IF stack.top NOT EQUAL to space -->prefixToInfix(stack)

それを少し勉強して、それをテストしてみてください（素晴らしい鉛筆と紙の方法で）。

Answer 2

例示的なオブジェクト指向のASTおよびパーサー：

$prefix = '* + 3 2 4';
$parser = new InfixPrefixParser($prefix);
$node = $parser->parse();
echo $node, "\n"; # ((3 + 2) * 4)
echo ' = ', $node->evaluate(), "\n"; # 20

パーサー：

class InfixPrefixParser extends IteratorIterator
{
    public function __construct($prefix)
    {
        $tokens = new ArrayIterator(preg_split('/\s/', $prefix, 0, PREG_SPLIT_NO_EMPTY));
        parent::__construct($tokens);
    }

    /**
     * @return InfixNode
     */
    public function current()
    {
        $string = parent::current();
        parent::next();
        $operators = array('*' => 'Mult', '+' => 'Plus');
        $class = 'InfixNode' . (isset($operators[$string]) ? 'Operator' . $operators[$string] : 'Value');
        $node = new $class($string);
        if ($node instanceof InfixNodeOperator) {
            $node->setLeft($this->current());
            $node->setRight($this->current());
        }
        return $node;
    }

    public function __toString()
    {
        return (string)$this->parse();
    }

    public function parse()
    {
        $this->rewind();
        return $this->current();
    }
}

ASTのオブジェクトモデル

abstract class InfixNode
{
    abstract function evaluate();
}

abstract class InfixNodeOperator extends InfixNode
{
    private $operator;
    protected $left;
    protected $right;

    public function __construct($operator)
    {
        $this->operator = $operator;
    }

    public function setLeft(InfixNode $node)
    {
        $this->left = $node;
    }

    public function getLeft()
    {
        return $this->left;
    }

    public function setRight(InfixNode $node)
    {
        $this->right = $node;
    }

    public function getRight()
    {
        return $this->right;
    }

    public function __toString()
    {
        return sprintf('(%s %s %s)', $this->left, $this->operator, $this->right);
    }
}

class InfixNodeOperatorMult extends InfixNodeOperator
{
    public function evaluate()
    {
        return $this->left->evaluate() * $this->right->evaluate();
    }
}

class InfixNodeOperatorPlus extends InfixNodeOperator
{
    public function evaluate()
    {
        return $this->left->evaluate() + $this->right->evaluate();
    }
}

class InfixNodeValue extends InfixNode
{
    private $value;

    public function __construct($value)
    {
        $this->value = $value;
    }

    public function __toString()
    {
        return (string)$this->value;
    }

    public function evaluate()
    {
        return $this->value;
    }
}

ノードは完全に中置に関連しているわけではないため、私は言葉遣いにあまり自信がありません。ノードの大部分は接頭辞または後置にも使用でき、__toString()実際には関数のみが中置に関連しています。

---

（旧バージョン）ノードの再帰解析関数とオブジェクトモデルを使用したPHPコード。使用法：

$prefix = '* + 3 2 4';

$tokens = new ArrayIterator(preg_split('/\s/', $prefix, 0, PREG_SPLIT_NO_EMPTY));

$parse = function() use ($tokens, &$parse) {
    $string = $tokens->current(); $tokens->next();
    $isOperator = in_array($string, array('*', '+'));
    $class = 'InfixNode' . ($isOperator ? 'Operator' : 'Value');
    $node = new $class($string);
    if ($node instanceof InfixNodeOperator) {
        $node->setLeft($parse());
        $node->setRight($parse());
    }
    return $node;
};

echo $parse(); # ((3 + 2) * 4)

ノードクラス：

class InfixNode {}

class InfixNodeOperator extends InfixNode
{
    private $operator;
    private $left;
    private $right;
    public function __construct($operator) {
        $this->operator = $operator;
    }
    public function setLeft(InfixNode $node) {
        $this->left = $node;
    }
    public function getLeft() {
        return $this->left;
    }
    public function setRight(InfixNode $node) {
        $this->right = $node;
    }
    public function getRight() {
        return $this->right;
    }
    public function __toString() {
        return sprintf('(%s %s %s)', $this->left, $this->operator, $this->right);
    }
}

class InfixNodeValue extends InfixNode
{
    private $value;
    public function __construct($value) {
        $this->value = $value;
    }
    public function __toString() {
        return (string) $this->value;
    }
}