求c语言函数递归问题 布尔表达式（用递归）

Question

描述

输入一个布尔表达式，请你输出它的真假值。
比如：( V | V ) & F & ( F | V )
V表示true，F表示false，&表示与，|表示或，!表示非。
上式的结果是F

输入

输入包含多行，每行一个布尔表达式，表达式中可以有空格，总长度不超过1000

输出

对每行输入，如果表达式为真，输出"V",否则出来"F"

样例输入

( V | V ) & F & ( F| V)
!V | V & V & !F & (F | V ) & (!F | F | !V & V)
(F&F|V|!V&!F&!(F|F&V))

样例输出

F
V
V

Answer 1

楼上的思维真是令人吃惊，又学到了一招。我也写了一种方法，虽然比楼上的复杂，既然写出来了，就给你看看吧。没有检测错误输入的功能，不想添加了。

#include <stdio.h>
#include <string.h>

bool Get_Result(char * buff,int start,int end); //求一个表达式的值
bool Char_BOOL(char ch); //求字符V和F的值
void Delete_Space(char * buff); //删除空格
void Delete_Brackets(char * buff); //删除括号
void Delete_Excl(char * buff); //删除感叹号

void main()
{
char buff[1000] = "";

while(gets(buff) != NULL)
{
Delete_Space(buff);
Delete_Brackets(buff);
Delete_Excl(buff);

if(Get_Result(buff,0,strlen(buff)-1))
printf("V\n");
else
printf("F\n");
}
return;
}

bool Char_BOOL(char ch)
{
if(ch == 'V' || ch == 'v')
return true;
return false;
}

bool Get_Result(char * buff,int start,int end)
{
bool result;
char test[1000];
int i;

for(i=start; i<=end; i++)
test[i-start] = buff[i];
test[i-start] = '\0';

Delete_Excl(test);

if(strlen(test) == 1)
return Char_BOOL(test[0]);
else if(strlen(test) == 2)
return !Char_BOOL(test[0]);
else if(strlen(test) == 3)
{
if(test[1] == '|')
return Char_BOOL(test[0]) | Char_BOOL(test[2]);
else if(test[1] == '&')
return Char_BOOL(test[0]) & Char_BOOL(test[2]);
else
return Char_BOOL(test[1]);
}
else
{
result = Get_Result(test,0,strlen(test)-3);
if(test[strlen(test)-2] == '|')
return result | Char_BOOL(test[strlen(test)-1]);
return result & Char_BOOL(test[strlen(test)-1]);
}

}

void Delete_Space(char * buff)
{
char test[1000];
int i,j,k;

k = strlen(buff);
j = 0;
for(i=0; i<k; i++)
{
if(buff[i] != ' ' && buff[i] != '\n')
{
test[j] = buff[i];
j++;
}
}
test[j] = '\0';
strcpy(buff,test);
}

void Delete_Brackets(char * buff)
{
int i,j;
int start,end;
char test[1000];

if(strchr(buff,'(') == NULL)
return;

j = strlen(buff);
for(i=j-1; i>=0; i--)
{
if(buff[i] == '(')
break;
}
start = i;
for(i=start+1; i<j; i++)
{
if(buff[i] == ')')
break;
}
end  = i;

buff[start] = '\0';
strcpy(test,buff+start+1);
test[end-start-1] = '\0';
if(Get_Result(test,0,strlen(test)))
sprintf(buff,"%sV%s",buff,buff+end+1);
else
sprintf(buff,"%sF%s",buff,buff+end+1);

Delete_Brackets(buff);
}

void Delete_Excl(char * buff)
{
char * pChar = NULL;
if((pChar = strchr(buff,'!')) == NULL)
return;
pChar[0] = '\0';

if(Char_BOOL(pChar[1]))
sprintf(buff,"%sF%s",buff,pChar+2);
else
sprintf(buff,"%sV%s",buff,pChar+2);

Delete_Excl(buff);
}

Answer 2

我下面的代码一次只处理一条表达式，你可以自己修改成处理多个表达式。

简单的代码说明：

get_value 用来获取一个 *原子* 表达式的值，所谓原子表达式是指 V, F, 或者用 () 括起来的组合表达式。它同时可处理前缀有 ! 的原子表达式。

eval_expr 用来处理一个组合表达式，所谓组合表达式是指一组由 &, | 连接起来的多个原子表达式的值。

具体处理方式很简单，get_value 如果碰到 V, F 那么直接返回 1 或 0, 如果 碰到 ! 则递归调用 get_value 获得下一个原子表达式的值，并取反返回。 如果碰到 ( 说明遇到组合表达式，它会调用 eval_expr 来获得组合表达式的值

同样的， eval_expr 会首先调用 get_value 来获得第一个原子表达式的值，然后如果碰到 | 则将当前值与下一个原子表达式的值做 OR 操作，如果碰到 & 则做 AND 操作。 如果遇到 ) 或者行尾则说明当前组合表达式处理完成，那么就返回当前组合表达式的值。

用户的输入总是被按照组合表达式的方式开始处理。

bool表达式的值只可能是 0 或者 1, 所以我用 -1 来做错误判断。

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>

#define LINE_SIZE 1000

static int inline AND(int x, int y)
{
    if (x < 0 || y < 0) return -1;
    return x && y;
}

static int inline OR(int x, int y)
{
    if (x < 0 || y < 0) return -1;
    return x || y;
}

static int inline NOT(int x)
{
    if (x < 0) return -1;
    return !x;
}

int get_value(const char *line, int len, int *idx)
{
    char ch = line[*idx];
    *idx += 1;
    
    switch (ch) {
    case 'V':
        return 1;
        
    case 'F':
        return 0;
        
    case '!':
        return (NOT(get_value(line, len, idx)));
        
    case '(':
        return eval_expr(line, len, idx);

    default:
        printf("Unexpected symbol '%c' at index %d\n", ch, *idx - 1);
        return -1;
    }
}

int eval_expr(const char *line, int len, int *idx)
{
    int value = -1, done = 0;
    char ch;
    
    for (; *idx < len && !done; ) {
        if (value < 0) {
            value = get_value(line, len, idx);
            if (value < 0)
                return -1;
            continue;
        }

        ch = line[*idx];
        *idx += 1;
        
        switch (ch) {
        case ')':
            done = 1;
            break;

        case '&':
            value = AND(value, get_value(line, len, idx));
            break;
            
        case '|':
            value = OR(value, get_value(line, len, idx));
            break;

        default:
            printf("Unexpected symbol '%c' at index %d\n", ch, *idx - 1);
            return -1;
        }
    }

    if (*idx >= len)
        done = 1;

    if (!done || value < 0) {
        printf("'%s' is not a valid expression\n", line);
        return -1;
    }

    return value;
}


int main()
{
    char ch, line[LINE_SIZE+1]; // +1 for trailing '\0'
    int i, j, v;

    while (i < LINE_SIZE) {
        ch = getchar();
        if (isblank(ch)) continue;
        if (ch == '\n' || ch == EOF) break;
        line[i++] = ch;
    }
    line[i] = '\0';
    j = 0;
    v = eval_expr(line, i, &j);
    if (i == j && v >= 0)
        printf("%s\n", v ? "V" : "F");
    return 0;
}

本回答被提问者采纳