- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
var fn={
'+':{priority:0,exec:function(a,b){return a+b}}
,'-':{priority:0,exec:function(a,b){return a-b}}
,'*':{priority:1,exec:function(a,b){return a*b}}
,'/':{priority:1,exec:function(a,b){return a/b}}
,'&':{priority:1,exec:function(a,b){return a&b}}
,'|':{priority:1,exec:function(a,b){return a|b}}
,'»':{priority:2,exec:function(a,b){return a>>b}}
,'«':{priority:2,exec:function(a,b){return a<<b}}
}
function exec(str){
var machine=putin();
var out=[];
console.log("Executing: "+str);
(str.trim()+" END").split(/\s+/).forEach(parser(function (e){
if (!e) throw "empty:"+e;
out.push(e);
machine.send(e);
}));
console.log(out.slice())
return machine.top();
}
function putin(){
// раз "единственно полезная структура данных"
var stack = [];
return {
send:function(e){
if (fn[e]){
b = stack.pop();
a = stack.pop();
r=fn[e].exec(a, b);
}else{
r=+e;
}
console.log(e,r);
stack.push(r);
},top:function(){return stack[0];}
}
}
function parser(output){
// джва "единственно полезная структура данных"
var ops=[];
var op2;
return function(e){
if (/[0-9]+/.test(e)) {
output(e);
}else if (null!=fn[e]){
op2=ops.slice(-1)[0];
while (fn[op2] && (fn[e].priority <= fn[op2].priority) ){
output(op2);
ops.pop();
op2 = ops.slice(-1)[0];
}
ops.push(e);
}else if (e == "(") {
ops.push(e);
}else if (e == ")") {
while (ops.slice(-1)[0] != "("){
output(ops.pop())
}
ops.pop();
}else if ("END" == e){
var x;
while (x=ops.pop(),x) {
output(x);
}
}else{
throw 'invalid pituh:'+e;
}
}
}
[
[-1187,"1 + 22 - 13 * ( 44 + 51 ) + 150 / 3 « 1"]
,[13,"1 + 3 * 4"]
,[16,"( 1 + 3 ) * 4"]
,[17," 1 + 2 * 3 - 4 * 5 + 10 * ( 12 - 9 )"]
]
.forEach(function (a){
if (a[0]!=exec(a[1])) throw ("Shit:"+ a[0]+" != "+ a[1])
});
После того как я заявил что массив — "единственно полезная структура данных", и можно парсить выражения без деревьев.
Гумно начало брать на «слабо».
Поточный парсер выражений, который принимает пайпом поток токенов и «на лету» пайпает свой выхлоп в интерпретатор.
Таким образом по мере прохождения потока он потихоньку исполняется и упрощается.
Follow us!