Btw, min första tanke var att skriva en lexer eller vad det heter och göra om uttrycket till ett AST. Men usch vad jobbigt det blev med prioriterings reglerna.
Här är min kod som jag gav upp med, den klarar i alla fall nivå 1.
<?php
/**
* The actual functions
*/
function F_ADD($a, $b) { return $a + $b; }
function F_MINUS($a, $b) { return $a - $b; }
function F_MULTIPLY($a, $b) { return $a * $b; }
function F_DIVIDE($a, $b) { return $a / $b; }
/**
* Tokens and their functions
*/
$op1 = array('F_ADD' => '+',
'F_MINUS' => '-');
$op2 = array('F_MULTIPLY' => '*',
'F_DIVIDE' => '/');
$num = array('0', '1', '2', '3', '4', '5', '6', '7', '8', '9');
//$tokens = ['NUM' => ['NUM', 'NEG_NUM'], 'OP' => ['OP1', 'OP2']]
/*
* TODO: Decimals
*/
function tokenize($str) {
global $op1, $op2, $num;
$input = str_split($str);
$out = array();
for($i = 0, $len = count($input); $i < $len; $i++) {
if($input[$i] == '-') {
if(in_array($input[$i - 1], $num)) {
$out[] = ['TOKEN' => 'OP1',
'VALUE' => array_search($input[$i], $op1)];
}
else {
$out[] = ['TOKEN' => 'NEG_NUM',
'VALUE' => '-'. $input[$i+1]];
$i++;
}
}
else if(in_array($input[$i], $num)) {
$value = $input[$i];
// Multi digit number
while(++$i < $len && in_array($input[$i], $num)) {
$value .= $input[$i];
}
$i--;
$out[] = ['TOKEN' => 'NUM',
'VALUE' => $value];
}
else if(in_array($input[$i], $op1))
$out[] = ['TOKEN' => 'OP1',
'VALUE' => array_search($input[$i], $op1)];
else if(in_array($input[$i], $op2))
$out[] = ['TOKEN' => 'OP2',
'VALUE' => array_search($input[$i], $op2)];
else if($input[$i] == '(')
$out[] = ['TOKEN' => 'GROUP_OPEN',
'VALUE' => $input[$i]];
else if($input[$i] == ')')
$out[] = ['TOKEN' => 'GROUP_CLOSE',
'VALUE' => $input[$i]];
}
return $out;
}
function operator_precedence($tokens) {
$out = $tokens;
$padding = 0;
foreach ($tokens as $i => $token) {
if($tokens[$i]['TOKEN'] == 'OP2') {
if($tokens[$i-1]['TOKEN'] == 'GROUP_CLOSE') {
//Find first GROUP_OPEN
foreach ($tokens as $key => $token2) {
if($token2['TOKEN'] == 'GROUP_OPEN') {
array_splice($out, $key, 0, [['TOKEN' => 'GROUP_OPEN', 'VALUE' => '(']]);
array_splice($out, $i+1+$padding +2, 0, [['TOKEN' => 'GROUP_CLOSE', 'VALUE' => ')']]);
break;
}
}
}
else if($tokens[$i+1]['TOKEN'] == 'GROUP_OPEN') {
foreach ($tokens as $key => $token2) {
if($token2['TOKEN'] == 'GROUP_CLOSE') {
array_splice($out, $i+1+$padding -2, 0, [['TOKEN' => 'GROUP_OPEN', 'VALUE' => '(']]);
array_splice($out, $key+1, 0, [['TOKEN' => 'GROUP_CLOSE', 'VALUE' => ')']]);
break;
}
}
}
else {
array_splice($out, $i+1+$padding -2, 0, [['TOKEN' => 'GROUP_OPEN', 'VALUE' => '(']]);
array_splice($out, $i+1+$padding +2, 0, [['TOKEN' => 'GROUP_CLOSE', 'VALUE' => ')']]);
}
$padding += 2; //Added two chrs to the array, so need to pad 2 steps
}
}
return $out;
}
function treelize($tokens, $index = 0) {
$out = [];
for($i = $index, $len = count($tokens); $i < $len; $i++) {
// Group, go one level deeper
if($tokens[$i]['TOKEN'] == 'GROUP_OPEN') {
$result = treelize($tokens, $i+1);
$i = $result['index'];
$out[] = $result['out'];
}
// Close group
else if($tokens[$i]['TOKEN'] == 'GROUP_CLOSE') {
return ['index' => $i,
'out' => $out];
}
// Normal case
else {
$out[] = ['VALUE' => $tokens[$i]['VALUE'],
'TOKEN' => $tokens[$i]['TOKEN']];
}
}
return ['index' => $i, 'out' => $out];
}
//Debug function
function flattern($tokens) {
$out = "";
foreach ($tokens as $token) {
$out .= $token['VALUE'] . " ";
}
return $out;
}
/**
* The function translate infix notation into polish notation.
*
* Turns 3*3+8 into * 3 + 3 8
* See it as: multiply(3, add(3, 8))
*
* Turns (3+3)*10 into * + 3 3 10
*
* Basically this function moves all operators one step to the left.
*/
function infix2polish($tree) {
global $op1, $op2, $num;
$out = [];
foreach ($tree as $i => $item) {
if(is_array(reset($item))) {
$out[$i] = infix2polish($item);
}
else if(in_array($item['TOKEN'], ['OP1', 'OP2'])) {
//Swap
$tmp = $out[$i - 1];
$out[$i - 1] = $item;
$out[$i] = $tmp;
}
else {
$out[$i] = $item;
}
}
return $out;
}
function run($tree) {
if(in_array($tree[0]['TOKEN'], ['OP1', 'OP2']))
{
//Array?
if(is_array(reset($tree[1])))
$x = run($tree[1]);
//OP?
else if(in_array($tree[1]['TOKEN'], ['OP1', 'OP2']))
$x = run(array_values(array_slice($tree, 1)));
//Num?
else if(in_array($tree[1]['TOKEN'], ['NUM', 'NEG_NUM']))
$x = intval($tree[1]['VALUE']);
//Array?
if(is_array(reset($tree[2])))
$y = run($tree[2]);
//OP?
else if(in_array($tree[2]['TOKEN'], ['OP1', 'OP2']))
$y = run(array_values(array_slice($tree, 2)));
//Num?
else if(in_array($tree[2]['TOKEN'], ['NUM', 'NEG_NUM']))
$y = intval($tree[2]['VALUE']);
return call_user_func($tree[0]['VALUE'], $x, $y);
}
// Handle special case like "3+(3)"
else {
return $tree[0]['VALUE'];
}
}
###########
# Main
###########
$input = $argv[1];
$tokens = tokenize($input);
print_r($tokens);
//$tokens = operator_precedence($tokens);
//print_r($tokens);
//echo flattern($tokens) . chr(10);
//echo $input . chr(10);
$tree = treelize($tokens);
print_r($tree['out']);
$functionized = infix2polish($tree['out']);
print_r($functionized);
$result = run($functionized);
print_r($result);
/*
(5+(3+3)*10)
(5+((3+3)*10))
3+3(*10)
10*(3+3)
(10*(3+3))
3*4*5
(3*4)*5
((3*4)*5)
//*/
?>
Programmerare -> PHP | HTML | CSS | JS | Java.
