php中缀的前缀[关闭](prefix to infix in php [closed])

php中缀的前缀[关闭](prefix to infix in php [closed])

我正在尝试在PHP中实现infix的前缀。 输入应该是这样的：

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

我想使用PHP或JavaScript (((3+2)*4))将前缀表达式(* + 3 2 4)如(* + 3 2 4)转换为中缀表达式。

I'm trying to implement prefix to infix in PHP. The input should be for example something like this:

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

I want to convert prefix expression like (* + 3 2 4) into infix expression using PHP or JavaScript (((3+2)*4)).

最满意答案

面向对象的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; } }

An exemplary object oriented AST and parser:

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

The parser:

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(); } }

The object model for the 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; } }

I'm not very confident with the wording, because the nodes aren't exactly fully related to infix, large parts of them could be used for prefix or postfix as well, only the __toString() functions are infix related actually.

---

(old version) Some PHP code, using some recursive parse function and an object model for the nodes. Usage:

$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)

The node classes:

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; } }