c - 递归检查C中方程的括号平衡

Question

我正在尝试用 C 编写一个程序，递归地检查方程式括号的平衡。 IE。每一次打开都有一个关闭。

这是我目前拥有的，但我无法让它忽略字符和空格。

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

#define MAX_SIZE 100

struct Stack{
    int top;
    char arr[MAX_SIZE];
} st;

void init(){
    st.top = -1;
}

bool isEmpty(){
    if(st.top == -1){
        return true;
    }else{
        return false;
    }
}

bool isFull(){
    if(st.top == MAX_SIZE-1){
        return true;
    }else{
        return false;
    }
}

void push(char item){
    if(isFull()){
            printf("Stack is full");
            exit(0);
    }else{
        st.top++;
        st.arr[st.top] = item;
    }
}

void pop(){
    if(isEmpty()){
        printf("Stack is empty");
        exit(0);
    }else{
        st.top--;
    }
}

char gettop(){
    return st.arr[st.top];
}

bool ArePair(char opening,char closing)
{
        if(opening == '(' && closing == ')') return true;
        else if(opening == '{' && closing == '}') return true;
        else if(opening == '[' && closing == ']') return true;
        return false;
}

void main()
{
    char in_expr[MAX_SIZE],a,temp;
    int length=0,i,j,count;

    init();
    printf("Enter an expression to check:");
    scanf("%s", in_expr);
    length = strlen(in_expr);

    for(i=0;i<length;i++){
         if (in_expr[i] !=  '(' && in_expr[i] != ')' && in_expr[i] != '{' && in_expr[i] != '}' && in_expr[i] != '[' && in_expr[i] !=  ']') {
                i++;
        }
        else if(in_expr[i] == '(' || in_expr[i] == '{' || in_expr[i] == '['){
                push(in_expr[i]);
                a = in_expr[i];
                printf("%c",a);
        }
        else if(in_expr[i] == ')' || in_expr[i] == '}' || in_expr[i] == ']'){
//                       a = st.arr[st.top];
                a = in_expr[i];
                printf("%c", a);
        }
        if(isEmpty() || !ArePair(gettop(),in_expr[i])){
          printf("\nInvalid expression - Not Balanced!\n");
                exit(0);
        }
        else{
                pop();
            }
        i++;
//        }
    }
    if(isEmpty()){
        printf("\nValid expression - Perfectly Balanced!\n");
    }else{
        printf("\nInvalid expression - Not Balanced!\n");
    }
}

非常感谢任何帮助，如果您需要更多详细信息，请随时询问!如果这是重复的，我深表歉意，我仍在通过此处的其他帖子寻找另一种解决方案。

Answer 1

一些错误:

不要在 for 子句中执行 i++ 。您 [可能] 跳过了您想查看的字符。

此外，不要检查 isEmpty 或 ArePair 除非当前字符更接近。

---

这是更正后的版本 [请原谅不必要的样式清理]。请注意，可能还有其他错误，但我认为这会让您更接近:

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

#define MAX_SIZE 100

struct Stack {
    int top;
    char arr[MAX_SIZE];
} st;

void
init()
{
    st.top = -1;
}

bool
isEmpty()
{
    if (st.top == -1) {
        return true;
    }
    else {
        return false;
    }
}

bool
isFull()
{
    if (st.top == MAX_SIZE - 1) {
        return true;
    }
    else {
        return false;
    }
}

void
push(char item)
{
    if (isFull()) {
        printf("Stack is full");
        exit(0);
    }
    else {
        st.top++;
        st.arr[st.top] = item;
    }
}

void
pop()
{
    if (isEmpty()) {
        printf("Stack is empty");
        exit(0);
    }
    else {
        st.top--;
    }
}

char
gettop()
{
    return st.arr[st.top];
}

bool
ArePair(char opening, char closing)
{
    if (opening == '(' && closing == ')')
        return true;
    else if (opening == '{' && closing == '}')
        return true;
    else if (opening == '[' && closing == ']')
        return true;
    return false;
}

void
main()
{
    char in_expr[MAX_SIZE],
     a,
     temp;
    int length = 0,
        i,
        j,
        count;

    init();
#if 0
    printf("Enter an expression to check:");
    scanf("%s", in_expr);
#else
    strcpy(in_expr,"( ( a + b ) * (c + d) ) * ( ( w + x ) * (y + z) )");
    //strcpy(in_expr,"( ( a + b ) * (c + d) ) * ( ( w + x ) * y + z) )");
#endif
    length = strlen(in_expr);

    for (i = 0; i < length; i++) {
        int chr = in_expr[i];
        printf("input: '%c'\n",chr);

        if (chr != '(' && chr != ')' && chr != '{' && chr != '}' && chr != '[' && chr != ']') {
            //i++;
            continue;
        }

        if (chr == '(' || chr == '{' || chr == '[') {
            push(chr);
            a = chr;
            printf("%c", a);
            continue;
        }

        if (chr == ')' || chr == '}' || chr == ']') {
            a = chr;
            printf("%c", a);
        }

        if (isEmpty() || !ArePair(gettop(), chr)) {
            printf("\nInvalid expression - Not Balanced!\n");
            exit(0);
        }
        else {
            pop();
        }
        //i++;
    }
    if (isEmpty()) {
        printf("\nValid expression - Perfectly Balanced!\n");
    }
    else {
        printf("\nInvalid expression - Not Balanced!\n");
    }
}

---

这是一个使用 switch 语句的版本，可能更容易阅读:

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

#define MAX_SIZE 100

struct Stack {
    int top;
    char arr[MAX_SIZE];
} st;

void
init()
{
    st.top = -1;
}

bool
isEmpty()
{
    if (st.top == -1) {
        return true;
    }
    else {
        return false;
    }
}

bool
isFull()
{
    if (st.top == MAX_SIZE - 1) {
        return true;
    }
    else {
        return false;
    }
}

void
push(char item)
{
    if (isFull()) {
        printf("Stack is full");
        exit(0);
    }
    else {
        st.top++;
        st.arr[st.top] = item;
    }
}

void
pop()
{
    if (isEmpty()) {
        printf("Stack is empty");
        exit(0);
    }
    else {
        st.top--;
    }
}

char
gettop()
{
    return st.arr[st.top];
}

bool
ArePair(char opening, char closing)
{
    if (opening == '(' && closing == ')')
        return true;
    else if (opening == '{' && closing == '}')
        return true;
    else if (opening == '[' && closing == ']')
        return true;
    return false;
}

void
main()
{
    char in_expr[MAX_SIZE],
     a,
     temp;
    int length = 0,
        i,
        j,
        count;

    init();
#if 0
    printf("Enter an expression to check:");
    scanf("%s", in_expr);
#else
    strcpy(in_expr,"( ( a + b ) * (c + d) ) * ( ( w + x ) * (y + z) )");
    //strcpy(in_expr,"( ( a + b ) * (c + d) ) * ( ( w + x ) * y + z) )");
#endif
    length = strlen(in_expr);

    for (i = 0; i < length; i++) {
        int chr = in_expr[i];
        printf("input: '%c'\n",chr);

        switch (chr) {
        case '(':
        case '{':
        case '[':
            push(chr);
            a = chr;
            printf("%c", a);
            break;
        }

        case ')':
        case '}':
        case ']':
            a = chr;
            printf("%c", a);
            if (isEmpty() || !ArePair(gettop(), chr)) {
                printf("\nInvalid expression - Not Balanced!\n");
                exit(0);
            }

            pop();
            break;
        }
    }

    if (isEmpty()) {
        printf("\nValid expression - Perfectly Balanced!\n");
    }
    else {
        printf("\nInvalid expression - Not Balanced!\n");
    }
}

---

这里是一个版本，增加了一个允许多个单元测试的自测试功能。这是我过去编写表达式解析器时所做的。

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

#define MAX_SIZE 100

struct Stack {
    int top;
    char arr[MAX_SIZE];
} st;

void
init()
{
    st.top = -1;
}

bool
isEmpty()
{
    if (st.top == -1) {
        return true;
    }
    else {
        return false;
    }
}

bool
isFull()
{
    if (st.top == MAX_SIZE - 1) {
        return true;
    }
    else {
        return false;
    }
}

void
push(char item)
{
    if (isFull()) {
        printf("Stack is full");
        exit(0);
    }
    else {
        st.top++;
        st.arr[st.top] = item;
    }
}

void
pop()
{
    if (isEmpty()) {
        printf("Stack is empty");
        exit(0);
    }
    else {
        st.top--;
    }
}

char
gettop()
{
    return st.arr[st.top];
}

bool
ArePair(char opening, char closing)
{
    if (opening == '(' && closing == ')')
        return true;
    else if (opening == '{' && closing == '}')
        return true;
    else if (opening == '[' && closing == ']')
        return true;
    return false;
}

// RETURNS: 1=balanced, 0=unbalanced
int
test_expr(const char *in_expr)
{
    int i;
    int length;

    //printf("\ntest_expr: '%s'\n",in_expr);

    init();
    length = strlen(in_expr);

    for (i = 0; i < length; i++) {
        int chr = in_expr[i];
        //printf("input: '%c'\n",chr);

        switch (chr) {
        case '(':
        case '{':
        case '[':
            push(chr);
            //printf("%c", chr);
            break;

        case ')':
        case '}':
        case ']':
            //printf("%c", chr);
            if (isEmpty() || !ArePair(gettop(), chr)) {
                printf("Invalid expression - Not Balanced!\n");
                return 0;
                exit(0);
            }

            pop();
            break;
        }
    }

    if (isEmpty()) {
        printf("Valid expression - Perfectly Balanced!\n");
        return 1;
    }
    else {
        printf("Invalid expression - Not Balanced!\n");
        return 0;
    }
}

void
testone(int expected,const char *expr)
{
    int isvalid;

    printf("\ntestone: '%s'\n",expr);
    isvalid = test_expr(expr);
    printf("%s\n", (isvalid == expected) ? "PASS" : "FAIL");
}

void
testall(void)
{

    testone(1,"( ( a + b ) * (c + d) ) * ( ( w + x ) * (y + z) )");
    testone(0," ( a + b ) * (c + d) ) * ( ( w + x ) * (y + z) )");
    testone(0,"( ( a + b ) * (c + d) ) * ( ( w + x ) * y + z) )");
    testone(0,"( ( a + b ) * (c + d) ) * ( ( w + x ) * (y + z) ");
    testone(0,"( ( a + b ) * (c + d) ) * ( ( w + x ) * (y + z )");
    testone(0,"( ( a + b ) * (c + d) ] * ( ( w + x ) * (y + z) )");
}

int
main(void)
{

#if 0
    char in_expr[MAX_SIZE];
    printf("Enter an expression to check:");
    scanf("%s", in_expr);
    test_expr(in_expr);
#else
    testall();
#endif

    return 0;
}