我正在尝试在 PHP 中实现前缀以中缀。例如,输入应该是这样的:
prefix * + 3 2 4
infix ((3+2)*4)
我想(* + 3 2 4)
使用 PHP 或 JavaScript 将前缀表达式转换为中缀表达式(((3+2)*4))
。
我正在尝试在 PHP 中实现前缀以中缀。例如,输入应该是这样的:
prefix * + 3 2 4
infix ((3+2)*4)
我想(* + 3 2 4)
使用 PHP 或 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;
}
}
这是前缀到后缀表示法的基本算法(使用 a 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)
试着研究一下,并测试它(用伟大的铅笔和纸方法)。