Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
With/without Intermediate Form (AST) comparison
const AST = {
Add: (left, right) => (cases) => cases['Add'](left, right),
Multiply: (left, right) => (cases) => cases['Multiply'](left, right),
Number: (value) => (cases) => cases['Number'](value)
}
const parse = (str) => {
const stack = []
str.split(' ').forEach(token => {
switch (token) {
default: {
stack.push(AST.Number(token))
break
}
case '+': {
const right = stack.pop()
const left = stack.pop()
stack.push(AST.Add(left, right))
break
}
case '*': {
const right = stack.pop()
const left = stack.pop()
stack.push(AST.Multiply(left, right))
break
}
}
})
return stack[0]
}
const evaluate = ast => ast({
Number: (v) => Number.parseInt(v, 10),
Multiply: (l, r) => evaluate(l) * evaluate(r),
Add: (l, r) => evaluate(l) + evaluate(r)
})
const toInfix = ast => ast({
Number: (v) => v,
Multiply: (l, r) => `(${toInfix(l)} * ${toInfix(r)})`,
Add: (l, r) => `(${toInfix(l)} + ${toInfix(r)})`
})
const toPolish = ast => ast({
Number: (v) => v,
Multiply: (l, r) => `* ${toPolish(l)} ${toPolish(r)}`,
Add: (l, r) => `+ ${toPolish(l)} ${toPolish(r)}`
})
const ast = parse('2 4 3 * +')
const result = evaluate(ast)
const equation = toInfix(ast)
console.log(`${equation} = ${result}`)
const AST = {
Add: (left, right) => ({ type: 'Add', left, right }),
Multiply: (left, right) => ({ type: 'Multiply', left, right }),
Number: (value) => ({ type: 'Number', value })
}
const parse = (str) => {
const stack = []
str.split(' ').forEach(token => {
switch (token) {
default: {
stack.push(AST.Number(token))
break
}
case '+': {
const right = stack.pop()
const left = stack.pop()
stack.push(AST.Add(left, right))
break
}
case '*': {
const right = stack.pop()
const left = stack.pop()
stack.push(AST.Multiply(left, right))
break
}
}
})
return stack[0]
}
const evaluate = ast => {
switch (ast.type) {
case 'Number': return Number.parseInt(ast.value, 10)
case 'Multiply': return evaluate(ast.left) * evaluate(ast.right)
case 'Add': return evaluate(ast.left) + evaluate(ast.right)
}
}
const toInfix = ast => {
switch (ast.type) {
case 'Number': return ast.value
case 'Multiply': return `(${toInfix(ast.left)} * ${toInfix(ast.right)})`
case 'Add': return `(${toInfix(ast.left)} + ${toInfix(ast.right)})`
}
}
const toPolish = ast => {
switch (ast.type) {
case 'Number': return ast.value
case 'Multiply': return `* ${toPolish(ast.left)} ${toPolish(ast.right)}`
case 'Add': return `+ ${toPolish(ast.left)} ${toPolish(ast.right)}`
}
}
const ast = parse('2 4 3 * +')
const result = evaluate(ast)
const equation = toInfix(ast)
console.log(`${equation} = ${result}`)
const evaluate = (str) => {
const stack = []
str.split(' ').forEach(token => {
switch (token) {
default: {
stack.push(Number.parseInt(token, 10))
break
}
case '+': {
const right = stack.pop()
const left = stack.pop()
stack.push(left + right)
break
}
case '*': {
const right = stack.pop()
const left = stack.pop()
stack.push(left * right)
break
}
}
})
return stack[0]
}
const equation = '2 4 3 * +'
const result = evaluate(equation)
console.log(`${equation} = ${result}`)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment