Boolean formula
Given an arbitrary formula of 2-valued Boolean algrebra, for instance (1V0)∧1V~(0∧1). How can I get a result of this formula using JavaScript ? I mean, a teacher gives a formula and my programm should print the result 1 or 0.
javascript boolean
asked Nov 25 '18 at 10:17
Dima GlushenkovDima Glushenkov
11
add a comment |
Given an arbitrary formula of 2-valued Boolean algrebra, for instance (1V0)∧1V~(0∧1). How can I get a result of this formula using JavaScript ? I mean, a teacher gives a formula and my programm should print the result 1 or 0.
javascript boolean
asked Nov 25 '18 at 10:17
Dima GlushenkovDima Glushenkov
11
This doesn't have to do specifically with javascript, I is the same as it would be in other languages too. Try replacing each logical operator with its equivalent in javascript. Also the 1 and 0 will probably be in the form of string so I would replace them withtrue,false.
– nikos fotiadis
Nov 25 '18 at 10:24
I think what OP means is that the program should act as interpreter and take textual form of this formula, and return the answer. But that's just my guess.
– bunglehead
Nov 25 '18 at 11:26
add a comment |
Given an arbitrary formula of 2-valued Boolean algrebra, for instance (1V0)∧1V~(0∧1). How can I get a result of this formula using JavaScript ? I mean, a teacher gives a formula and my programm should print the result 1 or 0.
javascript boolean
asked Nov 25 '18 at 10:17
Dima GlushenkovDima Glushenkov
11
Given an arbitrary formula of 2-valued Boolean algrebra, for instance (1V0)∧1V~(0∧1). How can I get a result of this formula using JavaScript ? I mean, a teacher gives a formula and my programm should print the result 1 or 0.
javascript boolean
javascript boolean
asked Nov 25 '18 at 10:17
Dima GlushenkovDima Glushenkov
11
asked Nov 25 '18 at 10:17
Dima GlushenkovDima Glushenkov
11
asked Nov 25 '18 at 10:17
Dima GlushenkovDima Glushenkov
11
asked Nov 25 '18 at 10:17
Dima GlushenkovDima Glushenkov
11
asked Nov 25 '18 at 10:17
Dima GlushenkovDima Glushenkov
11
11
This doesn't have to do specifically with javascript, I is the same as it would be in other languages too. Try replacing each logical operator with its equivalent in javascript. Also the 1 and 0 will probably be in the form of string so I would replace them withtrue,false.
– nikos fotiadis
Nov 25 '18 at 10:24
I think what OP means is that the program should act as interpreter and take textual form of this formula, and return the answer. But that's just my guess.
– bunglehead
Nov 25 '18 at 11:26
add a comment |
This doesn't have to do specifically with javascript, I is the same as it would be in other languages too. Try replacing each logical operator with its equivalent in javascript. Also the 1 and 0 will probably be in the form of string so I would replace them withtrue,false.
– nikos fotiadis
Nov 25 '18 at 10:24
I think what OP means is that the program should act as interpreter and take textual form of this formula, and return the answer. But that's just my guess.
– bunglehead
Nov 25 '18 at 11:26
This doesn't have to do specifically with javascript, I is the same as it would be in other languages too. Try replacing each logical operator with its equivalent in javascript. Also the 1 and 0 will probably be in the form of string so I would replace them with
true, false.– nikos fotiadis
Nov 25 '18 at 10:24
This doesn't have to do specifically with javascript, I is the same as it would be in other languages too. Try replacing each logical operator with its equivalent in javascript. Also the 1 and 0 will probably be in the form of string so I would replace them with
true, false.– nikos fotiadis
Nov 25 '18 at 10:24
I think what OP means is that the program should act as interpreter and take textual form of this formula, and return the answer. But that's just my guess.
– bunglehead
Nov 25 '18 at 11:26
I think what OP means is that the program should act as interpreter and take textual form of this formula, and return the answer. But that's just my guess.
– bunglehead
Nov 25 '18 at 11:26
add a comment |
3 Answers
3
active
oldest
votes
I guess the purpose of this exercise is to learn the basics of parsing and formal grammars. Here's some info to get you started.
First, you split the input into "tokens", or symbols (operators, values, parenthesis). This is called "lexing" and is rather trivial in your case, because your symbols are always one character.
Then, you build a parse tree, or "AST", from these tokens. Each node in the parse tree is an object operator left right, where left and right could be values or other node objects. For example,
a v b ^ c
yields the following parse tree
operator = v
left = a
right = {
operator = ^
left = b
right = c
}
To build a parser, you need to define a set of formal rules, called a "grammar", for your expressions. An example grammar for booleans:
<b-expression>::= <b-term> [OR <b-term>]*
<b-term> ::= <not-factor> [AND <not-factor>]*
<not-factor> ::= [NOT] <b-factor>
<b-factor> ::= <b-literal> | <b-variable> | (<b-expression>)
(https://compilers.iecc.com/crenshaw/tutor6.txt)
Once the AST is built, you "evaluate" each tree node with a simple recursive algorithm:
evaluate(node)
if node is a value (e.g. "1"), return this value
otherwise,
L = evaluate(node.left)
R = evaluate(node.right)
V = apply node.operator to L and R
return V
Hope this helps!
answered Nov 25 '18 at 10:48
georggeorg
151k35204301
add a comment |
You could use logical operators, like
- logical AND
&&
- logical OR
||
- logical NOT
!
and replace the given boolean operators.
console.log((1 || 0) && 1 || !(0 && 1));answered Nov 25 '18 at 10:21
Nina ScholzNina Scholz
190k1599173
add a comment |
If the input is always trustworthy, one option would be to transform the expression into proper JS syntax and then use eval:
const check = str => Boolean(eval(str
.replace(/v/gi, '||')
.replace(/∧/g, '&&')
.replace(/~/g, '!')
));
console.log(check('(1V0)∧1V~(0∧1)'));
console.log(check('0∧0'));
console.log(check('1∧1'));
console.log(check('1∧0'));
console.log(check('1V0'));
console.log(check('0V0'));answered Nov 25 '18 at 10:22
CertainPerformanceCertainPerformance
92.4k165383
well, I guess this is from the compilers class, and I don't think "use a compiler" is a right answer to the question "how to write a compiler". Like saying "get a taxi" to a driving school student. ;)
– georg
Nov 25 '18 at 11:00
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53466522%2fboolean-formula%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
I guess the purpose of this exercise is to learn the basics of parsing and formal grammars. Here's some info to get you started.
First, you split the input into "tokens", or symbols (operators, values, parenthesis). This is called "lexing" and is rather trivial in your case, because your symbols are always one character.
Then, you build a parse tree, or "AST", from these tokens. Each node in the parse tree is an object operator left right, where left and right could be values or other node objects. For example,
a v b ^ c
yields the following parse tree
operator = v
left = a
right = {
operator = ^
left = b
right = c
}
To build a parser, you need to define a set of formal rules, called a "grammar", for your expressions. An example grammar for booleans:
<b-expression>::= <b-term> [OR <b-term>]*
<b-term> ::= <not-factor> [AND <not-factor>]*
<not-factor> ::= [NOT] <b-factor>
<b-factor> ::= <b-literal> | <b-variable> | (<b-expression>)
(https://compilers.iecc.com/crenshaw/tutor6.txt)
Once the AST is built, you "evaluate" each tree node with a simple recursive algorithm:
evaluate(node)
if node is a value (e.g. "1"), return this value
otherwise,
L = evaluate(node.left)
R = evaluate(node.right)
V = apply node.operator to L and R
return V
Hope this helps!
answered Nov 25 '18 at 10:48
georggeorg
151k35204301
add a comment |
I guess the purpose of this exercise is to learn the basics of parsing and formal grammars. Here's some info to get you started.
First, you split the input into "tokens", or symbols (operators, values, parenthesis). This is called "lexing" and is rather trivial in your case, because your symbols are always one character.
Then, you build a parse tree, or "AST", from these tokens. Each node in the parse tree is an object operator left right, where left and right could be values or other node objects. For example,
a v b ^ c
yields the following parse tree
operator = v
left = a
right = {
operator = ^
left = b
right = c
}
To build a parser, you need to define a set of formal rules, called a "grammar", for your expressions. An example grammar for booleans:
<b-expression>::= <b-term> [OR <b-term>]*
<b-term> ::= <not-factor> [AND <not-factor>]*
<not-factor> ::= [NOT] <b-factor>
<b-factor> ::= <b-literal> | <b-variable> | (<b-expression>)
(https://compilers.iecc.com/crenshaw/tutor6.txt)
Once the AST is built, you "evaluate" each tree node with a simple recursive algorithm:
evaluate(node)
if node is a value (e.g. "1"), return this value
otherwise,
L = evaluate(node.left)
R = evaluate(node.right)
V = apply node.operator to L and R
return V
Hope this helps!
answered Nov 25 '18 at 10:48
georggeorg
151k35204301
add a comment |
I guess the purpose of this exercise is to learn the basics of parsing and formal grammars. Here's some info to get you started.
First, you split the input into "tokens", or symbols (operators, values, parenthesis). This is called "lexing" and is rather trivial in your case, because your symbols are always one character.
Then, you build a parse tree, or "AST", from these tokens. Each node in the parse tree is an object operator left right, where left and right could be values or other node objects. For example,
a v b ^ c
yields the following parse tree
operator = v
left = a
right = {
operator = ^
left = b
right = c
}
To build a parser, you need to define a set of formal rules, called a "grammar", for your expressions. An example grammar for booleans:
<b-expression>::= <b-term> [OR <b-term>]*
<b-term> ::= <not-factor> [AND <not-factor>]*
<not-factor> ::= [NOT] <b-factor>
<b-factor> ::= <b-literal> | <b-variable> | (<b-expression>)
(https://compilers.iecc.com/crenshaw/tutor6.txt)
Once the AST is built, you "evaluate" each tree node with a simple recursive algorithm:
evaluate(node)
if node is a value (e.g. "1"), return this value
otherwise,
L = evaluate(node.left)
R = evaluate(node.right)
V = apply node.operator to L and R
return V
Hope this helps!
answered Nov 25 '18 at 10:48
georggeorg
151k35204301
I guess the purpose of this exercise is to learn the basics of parsing and formal grammars. Here's some info to get you started.
First, you split the input into "tokens", or symbols (operators, values, parenthesis). This is called "lexing" and is rather trivial in your case, because your symbols are always one character.
Then, you build a parse tree, or "AST", from these tokens. Each node in the parse tree is an object operator left right, where left and right could be values or other node objects. For example,
a v b ^ c
yields the following parse tree
operator = v
left = a
right = {
operator = ^
left = b
right = c
}
To build a parser, you need to define a set of formal rules, called a "grammar", for your expressions. An example grammar for booleans:
<b-expression>::= <b-term> [OR <b-term>]*
<b-term> ::= <not-factor> [AND <not-factor>]*
<not-factor> ::= [NOT] <b-factor>
<b-factor> ::= <b-literal> | <b-variable> | (<b-expression>)
(https://compilers.iecc.com/crenshaw/tutor6.txt)
Once the AST is built, you "evaluate" each tree node with a simple recursive algorithm:
evaluate(node)
if node is a value (e.g. "1"), return this value
otherwise,
L = evaluate(node.left)
R = evaluate(node.right)
V = apply node.operator to L and R
return V
Hope this helps!
answered Nov 25 '18 at 10:48
georggeorg
151k35204301
edited Nov 25 '18 at 11:12
answered Nov 25 '18 at 10:48
georggeorg
151k35204301
answered Nov 25 '18 at 10:48
georggeorg
151k35204301
answered Nov 25 '18 at 10:48
georggeorg
151k35204301
151k35204301
add a comment |
add a comment |
You could use logical operators, like
- logical AND
&&
- logical OR
||
- logical NOT
!
and replace the given boolean operators.
console.log((1 || 0) && 1 || !(0 && 1));answered Nov 25 '18 at 10:21
Nina ScholzNina Scholz
190k1599173
add a comment |
You could use logical operators, like
- logical AND
&&
- logical OR
||
- logical NOT
!
and replace the given boolean operators.
console.log((1 || 0) && 1 || !(0 && 1));answered Nov 25 '18 at 10:21
Nina ScholzNina Scholz
190k1599173
add a comment |
You could use logical operators, like
- logical AND
&&
- logical OR
||
- logical NOT
!
and replace the given boolean operators.
console.log((1 || 0) && 1 || !(0 && 1));answered Nov 25 '18 at 10:21
Nina ScholzNina Scholz
190k1599173
You could use logical operators, like
- logical AND
&&
- logical OR
||
- logical NOT
!
and replace the given boolean operators.
console.log((1 || 0) && 1 || !(0 && 1)); console.log((1 || 0) && 1 || !(0 && 1)); console.log((1 || 0) && 1 || !(0 && 1));answered Nov 25 '18 at 10:21
Nina ScholzNina Scholz
190k1599173
answered Nov 25 '18 at 10:21
Nina ScholzNina Scholz
190k1599173
answered Nov 25 '18 at 10:21
Nina ScholzNina Scholz
190k1599173
answered Nov 25 '18 at 10:21
Nina ScholzNina Scholz
190k1599173
190k1599173
add a comment |
add a comment |
If the input is always trustworthy, one option would be to transform the expression into proper JS syntax and then use eval:
const check = str => Boolean(eval(str
.replace(/v/gi, '||')
.replace(/∧/g, '&&')
.replace(/~/g, '!')
));
console.log(check('(1V0)∧1V~(0∧1)'));
console.log(check('0∧0'));
console.log(check('1∧1'));
console.log(check('1∧0'));
console.log(check('1V0'));
console.log(check('0V0'));answered Nov 25 '18 at 10:22
CertainPerformanceCertainPerformance
92.4k165383
well, I guess this is from the compilers class, and I don't think "use a compiler" is a right answer to the question "how to write a compiler". Like saying "get a taxi" to a driving school student. ;)
– georg
Nov 25 '18 at 11:00
add a comment |
If the input is always trustworthy, one option would be to transform the expression into proper JS syntax and then use eval:
const check = str => Boolean(eval(str
.replace(/v/gi, '||')
.replace(/∧/g, '&&')
.replace(/~/g, '!')
));
console.log(check('(1V0)∧1V~(0∧1)'));
console.log(check('0∧0'));
console.log(check('1∧1'));
console.log(check('1∧0'));
console.log(check('1V0'));
console.log(check('0V0'));answered Nov 25 '18 at 10:22
CertainPerformanceCertainPerformance
92.4k165383
well, I guess this is from the compilers class, and I don't think "use a compiler" is a right answer to the question "how to write a compiler". Like saying "get a taxi" to a driving school student. ;)
– georg
Nov 25 '18 at 11:00
add a comment |
If the input is always trustworthy, one option would be to transform the expression into proper JS syntax and then use eval:
const check = str => Boolean(eval(str
.replace(/v/gi, '||')
.replace(/∧/g, '&&')
.replace(/~/g, '!')
));
console.log(check('(1V0)∧1V~(0∧1)'));
console.log(check('0∧0'));
console.log(check('1∧1'));
console.log(check('1∧0'));
console.log(check('1V0'));
console.log(check('0V0'));answered Nov 25 '18 at 10:22
CertainPerformanceCertainPerformance
92.4k165383
If the input is always trustworthy, one option would be to transform the expression into proper JS syntax and then use eval:
const check = str => Boolean(eval(str
.replace(/v/gi, '||')
.replace(/∧/g, '&&')
.replace(/~/g, '!')
));
console.log(check('(1V0)∧1V~(0∧1)'));
console.log(check('0∧0'));
console.log(check('1∧1'));
console.log(check('1∧0'));
console.log(check('1V0'));
console.log(check('0V0'));const check = str => Boolean(eval(str
.replace(/v/gi, '||')
.replace(/∧/g, '&&')
.replace(/~/g, '!')
));
console.log(check('(1V0)∧1V~(0∧1)'));
console.log(check('0∧0'));
console.log(check('1∧1'));
console.log(check('1∧0'));
console.log(check('1V0'));
console.log(check('0V0'));const check = str => Boolean(eval(str
.replace(/v/gi, '||')
.replace(/∧/g, '&&')
.replace(/~/g, '!')
));
console.log(check('(1V0)∧1V~(0∧1)'));
console.log(check('0∧0'));
console.log(check('1∧1'));
console.log(check('1∧0'));
console.log(check('1V0'));
console.log(check('0V0'));answered Nov 25 '18 at 10:22
CertainPerformanceCertainPerformance
92.4k165383
answered Nov 25 '18 at 10:22
CertainPerformanceCertainPerformance
92.4k165383
answered Nov 25 '18 at 10:22
CertainPerformanceCertainPerformance
92.4k165383
answered Nov 25 '18 at 10:22
CertainPerformanceCertainPerformance
92.4k165383
92.4k165383
well, I guess this is from the compilers class, and I don't think "use a compiler" is a right answer to the question "how to write a compiler". Like saying "get a taxi" to a driving school student. ;)
– georg
Nov 25 '18 at 11:00
add a comment |
well, I guess this is from the compilers class, and I don't think "use a compiler" is a right answer to the question "how to write a compiler". Like saying "get a taxi" to a driving school student. ;)
– georg
Nov 25 '18 at 11:00
well, I guess this is from the compilers class, and I don't think "use a compiler" is a right answer to the question "how to write a compiler". Like saying "get a taxi" to a driving school student. ;)
– georg
Nov 25 '18 at 11:00
well, I guess this is from the compilers class, and I don't think "use a compiler" is a right answer to the question "how to write a compiler". Like saying "get a taxi" to a driving school student. ;)
– georg
Nov 25 '18 at 11:00
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53466522%2fboolean-formula%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
This doesn't have to do specifically with javascript, I is the same as it would be in other languages too. Try replacing each logical operator with its equivalent in javascript. Also the 1 and 0 will probably be in the form of string so I would replace them with
true,false.– nikos fotiadis
Nov 25 '18 at 10:24
I think what OP means is that the program should act as interpreter and take textual form of this formula, and return the answer. But that's just my guess.
– bunglehead
Nov 25 '18 at 11:26