我有一个 C 语言程序，可以用 MPI 解决电路可满足性问题。该电路可以包含 AND、OR 和 NOT 门。
在我的程序中，电路是“硬编码”的，如下所示：
( v[0] || v[1] ) && ( !v[1] || !v[3] ) && ( v[2] || v[3] )
带映射：|| = OR, && = AND, ! = NOT
v[0], v[1], etc 是 0 和 1 的数组
在某些时候，我像这样评估电路：
value = ( v[0] || v[1] ) && ( !v[1] || !v[3] ) && ( v[2] || v[3] );
我想测试从文本文件中读取的多个电路。现在，我的问题是：如何在 C 中将字符串转换为逻辑表达式？
基本上，我想要像 value = 'string from file here' 这样的东西。
有什么建议么？
行。我已经修改Shunting-Yard了使用布尔表达式的算法。
这是评估布尔表达式的代码：
#include <string.h>
#include <stdio.h>
#define bool int
#define false 0
#define true 1
int op_preced(const char c)
{
switch(c) {
case '|':
return 6;
case '&':
return 5;
case '!':
return 4;
case '*': case '/': case '%':
return 3;
case '+': case '-':
return 2;
case '=':
return 1;
}
return 0;
}
bool op_left_assoc(const char c)
{
switch(c) {
// left to right
case '*': case '/': case '%': case '+': case '-': case '|': case '&':
return true;
// right to left
case '=': case '!':
return false;
}
return false;
}
unsigned int op_arg_count(const char c)
{
switch(c) {
case '*': case '/': case '%': case '+': case '-': case '=': case '&': case '|':
return 2;
case '!':
return 1;
default:
return c - 'A';
}
return 0;
}
#define is_operator(c) (c == '+' || c == '-' || c == '/' || c == '*' || c == '!' || c == '%' || c == '=' || c == '&' || c == '|')
#define is_function(c) (c >= 'A' && c <= 'Z')
#define is_ident(c) ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z'))
bool shunting_yard(const char *input, char *output)
{
const char *strpos = input, *strend = input + strlen(input);
char c, *outpos = output;
char stack[32]; // operator stack
unsigned int sl = 0; // stack length
char sc; // used for record stack element
while(strpos < strend) {
// read one token from the input stream
c = *strpos;
if(c != ' ') {
// If the token is a number (identifier), then add it to the output queue.
if(is_ident(c)) {
*outpos = c; ++outpos;
}
// If the token is a function token, then push it onto the stack.
else if(is_function(c)) {
stack[sl] = c;
++sl;
}
// If the token is a function argument separator (e.g., a comma):
else if(c == ',') {
bool pe = false;
while(sl > 0) {
sc = stack[sl - 1];
if(sc == '(') {
pe = true;
break;
}
else {
// Until the token at the top of the stack is a left parenthesis,
// pop operators off the stack onto the output queue.
*outpos = sc;
++outpos;
sl--;
}
}
// If no left parentheses are encountered, either the separator was misplaced
// or parentheses were mismatched.
if(!pe) {
printf("Error: separator or parentheses mismatched\n");
return false;
}
}
// If the token is an operator, op1, then:
else if(is_operator(c)) {
while(sl > 0) {
sc = stack[sl - 1];
if(is_operator(sc) &&
((op_left_assoc(c) && (op_preced(c) >= op_preced(sc))) ||
(op_preced(c) > op_preced(sc)))) {
// Pop op2 off the stack, onto the output queue;
*outpos = sc;
++outpos;
sl--;
}
else {
break;
}
}
// push op1 onto the stack.
stack[sl] = c;
++sl;
}
// If the token is a left parenthesis, then push it onto the stack.
else if(c == '(') {
stack[sl] = c;
++sl;
}
// If the token is a right parenthesis:
else if(c == ')') {
bool pe = false;
// Until the token at the top of the stack is a left parenthesis,
// pop operators off the stack onto the output queue
while(sl > 0) {
sc = stack[sl - 1];
if(sc == '(') {
pe = true;
break;
}
else {
*outpos = sc;
++outpos;
sl--;
}
}
// If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
if(!pe) {
printf("Error: parentheses mismatched\n");
return false;
}
// Pop the left parenthesis from the stack, but not onto the output queue.
sl--;
// If the token at the top of the stack is a function token, pop it onto the output queue.
if(sl > 0) {
sc = stack[sl - 1];
if(is_function(sc)) {
*outpos = sc;
++outpos;
sl--;
}
}
}
else {
printf("Unknown token %c\n", c);
return false; // Unknown token
}
}
++strpos;
}
// When there are no more tokens to read:
// While there are still operator tokens in the stack:
while(sl > 0) {
sc = stack[sl - 1];
if(sc == '(' || sc == ')') {
printf("Error: parentheses mismatched\n");
return false;
}
*outpos = sc;
++outpos;
--sl;
}
*outpos = 0; // Null terminator
return true;
}
bool evalBoolExpr(char * expr) {
char output[500] = {0};
char * op;
bool tmp;
char part1[250], part2[250];
if(!shunting_yard(expr, output))
return false; // oops can't convert to postfix form
while (strlen(output) > 1) {
op = &output[0];
while (!is_operator(*op) && *op != '\0')
op++;
if (*op == '\0') {
return false; // oops - zero operators found
}
else if (*op == '!') {
tmp = !(*(op-1) - 48);
*(op-1) = '\0';
}
else if(*op == '&') {
tmp = (*(op-1) - 48) && (*(op-2) - 48);
*(op-2) = '\0';
}
else if (*op == '|') {
tmp = (*(op-1) - 48) || (*(op-2) - 48);
*(op-2) = '\0';
}
memset(part1, 0, sizeof(part1));
memset(part2, 0, sizeof(part2));
strcpy(part1, output);
strcpy(part2, op+1);
memset(output, 0, sizeof(output));
strcat(output, part1);
strcat(output, ((tmp==false) ? "0" : "1"));
strcat(output, part2);
}
return *output - 48;
}
int main() {
char * boolString[2] = {"FALSE", "TRUE"};
char * expr = "!((1 | 0) & (1 & ((1 & !0) | 0)))";
bool result = evalBoolExpr(expr);
printf("Boolean expr. %s is %s", expr, boolString[result]);
return 0;
}
只需将&/|符号放在逻辑表达式中，而不是 double &&/ ||。
您可以构建一个简单的虚拟机或构建一个从文本文件读取的解析器。两者都可以，这取决于您想要什么。拥有“来自文本文件的 c 中的有效逻辑表达式”不会很好地工作。C 不是脚本语言，在运行时不会运行新代码。这将需要虚拟机 (LUA) 或解析器。我构建了一个小型虚拟机，它执行一小组指令（5 或 6 条），可以进行加法、减法、乘法、除法等。你可以实现门（即 OR = 0x01，AND = 0x02）和你的文本文件将只包含二进制的一些二进制或十六进制表示。
这会增加一些复杂性，并且要在编写文本文件时变得非常有效，您需要实现某种编译器，除非您想手动编写二进制文件（使用少量指令不会太糟了）。
你可以在 Github 上查看一些示例，并且有很多在线网站可以解释简单的虚拟机。
您需要为您的表达式编写一些解析器。也许像ANTLR（或flex & bison）这样的工具可以提供帮助。我建议解析为一些抽象语法树，然后将该 AST 评估为您的值。
您也许还可以考虑在程序中嵌入解释器（例如Lua）
也许你也可以考虑将你的表达式翻译成 C 代码。或者只是#include-ing 一个包含它们的文件。
一种可能是generated.c在运行时生成一个正确的 C 源文件，其中包含一些函数的 C 源代码（您可以从一些已解析的 AST 发出），然后编译它（例如，假设一个 Linux 系统，通过分叉一些gcc -Wall -O -fPIC -shared generated.c -o generated.so命令） ，然后动态加载./generated.so使用dlopen(3)生成的 so并使用dlsym(3)在那里找到相关的函数地址（因此您可以将它们用作函数指针并调用它们）。FWIW，扩展 GCC 的MELT领域特定语言成功地做到了这一点。
我仍然不完全了解您要做什么以及您要问什么