MPIで回路充足可能性を解決するC言語のプログラムがあります。回路には、AND、OR、および NOT ゲートを含めることができます。
私のプログラムでは、回路は次のように「ハードコード」されています。
( v[0] || v[1] ) && ( !v[1] || !v[3] ) && ( v[2] || v[3] )
マッピングあり:|| = OR, && = AND, ! = NOT
v[0], v[1]などは 0 と 1 の配列
ある時点で、次のように回路を評価します。
value = ( v[0] || v[1] ) && ( !v[1] || !v[3] ) && ( v[2] || v[3] );
テキストファイルから読み取った複数の回路をテストしたい。さて、私の質問は次のとおりです。Cで文字列から論理式に変換するにはどうすればよいですか?
基本的に、 value = 'string from file here' のようなものが欲しいです。
助言がありますか？
Ok。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) とテキストファイルには、バイナリのバイナリまたは 16 進表現が含まれているだけです。
これにより複雑さが増し、テキスト ファイルの書き込みを非常に効果的に行うには、何らかのコンパイラを実装する必要があります。残念）。
Github でいくつかの例を確認できます。オンラインには、単純な仮想マシンについて説明しているサイトがたくさんあります。
式のパーサーを作成する必要があります。おそらくANTLR (またはflex & bison ) のようなツールが役立つでしょう。いくつかの抽象構文ツリーに解析してから、その AST を値として評価することをお勧めします。
おそらく、プログラムにインタープリター (例: Lua ) を埋め込むことも検討できます。
式を C コードに変換することも検討できるかもしれません。または#include、それらを含むファイルを単に -ing します。
実行時に正しい C ソース ファイルを生成し、generated.cいくつかの関数の C ソース コード (解析された AST から発行できる) を含み、それをコンパイルする (たとえば、Linux システムを仮定すると、いくつかのgcc -Wall -O -fPIC -shared generated.c -o generated.soコマンドを fork することによって)可能性があります。 、次にdlopen(3)./generated.soで生成されたものを動的にロードし、dlsym(3)を使用して関連する関数アドレスを見つけます (したがって、それらを関数ポインターとして使用してこれらを呼び出すことができます)。FWIW、GCCを拡張するためのMELTドメイン固有言語はそれをうまく行います。
あなたが何をしようとしているのか、何を求めているのか、私はまだ正確に理解していません