C语言 平衡的表达

Question

下面是确定符号平衡的代码。

如果表达式是平衡的，那么它应该打印适当的消息。例句:

((A+B))+(C+D)) --> Balanced
((A+B)+(C+D) ---> Unbalanced
((A+B)+(C+D}) --> Unbalanced

代码

#include <stdio.h>
#include <stdlib.h>
struct Stack {
    char data;
    struct Stack *next;
};
void push(struct Stack **top, char data) {
    struct Stack *new_node;
    if (*top == NULL) {
        new_node = malloc(sizeof(struct Stack));
        new_node->data = data;
        new_node->next = *top;
        *top = new_node;
    } else {
        new_node = malloc(sizeof(struct Stack));
        new_node->data = data;
        new_node->next = *top;
        *top = new_node;
    }
}
char pop(struct Stack **top, int flag) {
    if (*top != NULL && flag == 0) {
        printf("n Expression is In-Valid  :) n");
        return '';
    }
    if (*top == NULL && flag == 1) {
        printf("n Unbalanced Expression n");
        return '';
    }
    if (*top != NULL && flag == 1) {
        struct Stack *temp = *top;
        char op;
        op = (*top)->data;
        *top = (*top)->next;
        free(temp);
        return op;
    }
}
/*
void display(struct Stack *top) {
    struct Stack *temp = top;
    while (temp) {
        printf("n %c", temp->data);
        temp = temp->next;
    }
}
*/
int main(void) {
    struct Stack *top = NULL;
    int i = 0;
    char str[] = "((A+B)+[C+D])", op;
    printf("n Running the programe to check if the string is balanced or not ");
    for (i = 0; str[i] != ''; ++i) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{' || str[i] == '<')
            push(&top, str[i]);
        else
        if (str[i] == ')' || str[i] == ']' || str[i] == '}' || str[i] == '>') {
            op = pop(&top, 1);
            if ((op == '(' && str[i] == ')') || 
                (op == '[' && str[i] == ']') ||
                (op == '{' && str[i] == '}') ||
                (op == '<' && str[i] == '>')) {
                continue;
            } else {
                printf("n The expression is un-balanced n");
                break;
            }
        }
    }
    pop(&top, 0);
    return 0;
}

但是它没有给出期望的输出。我已经调试了代码，但没有找到问题。

如何让它打印出合适的信息?

Answer 1

一旦检测到不平衡，应该立即清理堆栈并停止处理，并在到达返回0时打印"Balanced"。你应该在代码的一个地方打印" balanced"。

并且pop的一个分支在声明返回值时没有返回值，这是很糟糕的。

因此，pop可以变成:

char pop(struct Stack **top,int flag)
{
        if(*top!=NULL && flag==0)
        {
                return '';
        }
        if(*top==NULL && flag ==1)
        {
                return '';
        }
        if(*top!=NULL && flag==1)
        {
                struct Stack *temp=*top;
                char op;
                op=(*top)->data;
                *top=(*top)->next;
                free(temp);
                return op;
        }
        // *top == null && flag == 0
        return 'O'; // for OK
}

我会添加一个clean方法-不是必需的，因为程序退出会清理堆栈，但我更喜欢:

void clean(struct Stack *top) {
    struct Stack *next;
    while (top != NULL) {
        next = top->next;
        free(top);
        top = next;
    }
}

和main中的一些变化:

int main(void)
{
        struct Stack *top=NULL;
        int i=0, err=0;
        ...
                        else
                        {
                                err = 1;
                                break;
                        }
                }
        }
        if (err || (pop(&top,0) == '')) {
            printf("n The expression is un-balanced n");
            clean(top);
            // return 1; optionally if you want to return a different value to environment
        }
        else {
            printf("n The expression is balanced n");
        }
        return 0;
}

Answer 2

你的pop函数是错误的。

如果top是null, flag是0，您没有处理。

其次，当你应该传递top时，为什么在pushpop签名中传递**top ?我觉得签名里应该有*top

还有，为什么在push中使用if。不需要。

Answer 3

您可以在这段代码中进行简单的修改。我把它从查找最大深度嵌套括号在一个字符串这个。这也有助于了解细节。我认为这对你有帮助。

#include <iostream>
using namespace std;
// function takes a string and returns the
// maximum depth nested parenthesis
int maxDepth(string S)
{
    int current_max = 0; // current count
    int max = 0;    // overall maximum count
    int n = S.length();
    // Traverse the input string
    for (int i = 0; i< n; i++)
    {
        if (S[i] == '(')
        {
            current_max++;
            // update max if required
            if (current_max> max)
                max = current_max;
        }
        else if (S[i] == ')')
        {
            if (current_max>0)
                current_max--;
            else
                return -1;
        }
    }
    // finally check for unbalanced string
    if (current_max != 0)
        return -1;
    return max;
}
// Driver program
int main()
{
    string s = "( ((X)) (((Y))) )";
    if (maxDepth(s) == -1)    
        cout << "Unbalance";
    else 
        cout << "Balance";
    return 0;
}

Time Complexity : O(n)
Auxiliary Space : O(1)

Answer 4

谢谢你的建议。这是我下面的相同问题的工作代码

#include<stdio.h>
#include<stdlib.h>
struct Stack{
char data;
struct Stack *next;
};
void push(struct Stack **top,char data)
{
        struct Stack *new_node;
        new_node=malloc(sizeof(struct Stack));
        new_node->data=data;
        new_node->next=*top;
        *top=new_node;
}
int compare(char str,char op)
{
        if( (op == '(' && str == ')') || (op == '{' && str == '}') || (op == '[' && str == ']') || (op == '<' && str == '>') )
                return 1;
        else
                return 0;
}
int pop(struct Stack **top,char str)
{
        char op,ret;
        struct Stack *temp=*top;
        if(*top==NULL)
                return 0;
        else if(*top!=NULL)
        {
                // Pop the element and then call comapre function
                op=(*top)->data;
                free(temp);
                *top=(*top)->next;
                return(ret=compare(str,op));
        }
}
void display(struct Stack *top)
{
        struct Stack *temp=top;
        while(temp!=NULL)
        {
                printf("%c ",temp->data);
                temp=temp->next;
        }
printf("n");
}
int isNotEmpty(struct Stack *top)
{
        if(top!=NULL)
                return 1;
        else
                return 0;
}
int main(void)
{
        struct Stack *top=NULL;
        int i=0,y,flag=0;
        char str[]="((A+B)+(C+D)>",op;
        printf("n Running the programe to check if the string is balanced or not ");
        for(i=0;str[i]!='';++i)
        {
                if( str[i] == '(' || str[i] == '[' || str[i] == '{' || str[i] == '<' )
                        push(&top,str[i]);
                else if( str[i] == ')' || str[i] == ']' || str[i] == '}' || str[i] == '>')
                {
                        y=pop(&top,str[i]);
                        if(!y)
                        {
                                printf("n Unbalanced Expression ");
                                flag=1;
                        }
                }
        }
        if(!flag)
        {
                if(isNotEmpty(top))
                        printf(" nUnbalanced Expression ");
                else
                        printf(" n Balanced Expression ");
        }
        printf("n");
        return 0;
}

Answer 5

检查这段代码，它是超级容易和容易理解

package com.codewithsouma.stack;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
public class Expression {
    private final List<Character> leftBrackets = Arrays.asList('(','{','[','<');
    private final List<Character> rightBrackets = Arrays.asList(')','}',']','>');
    public boolean isBalanced(String input) {
        Stack<Character> stack = new Stack<>();
        for (char ch : input.toCharArray()) {
            if (isLeftBracket(ch))
                stack.push(ch);
            if (isRightBracket(ch)) {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if (!bracketsMatch(top,ch)) return false;
            }
        }
        return stack.isEmpty();
    }
    private boolean isRightBracket(char ch) {
        return rightBrackets.contains(ch);
    }
    private boolean isLeftBracket(char ch) {
        return leftBrackets.contains(ch);
    }
    public boolean bracketsMatch(char left, char right){
        return leftBrackets.indexOf(left) == rightBrackets.indexOf(right);
    }
}

Answer 6

首先，我们创建一个哈希表并存储所有括号，左括号是键，值是它对应的右括号。然后从用户处获取一个表达式字符串并创建一个字符数组。然后迭代数组,然后我们检查这个字符左括号不信如果是左括号然后放入堆栈(leftBracketContainer)否则我们检查它是正确的支架如果右括号然后我们流行的左括号堆栈和发现对面的括号/支架从哈希表和匹配当前字符/支架如果不匹配(例如我们的堆栈包含{这架其关闭括号}我们发现从散列映射和当前字符=]当前字符!=对括号)return false，否则继续。最后，当循环结束时，堆栈应该清空。(如果堆栈中多一个左括号，则表示表达式需要另一个右括号)如果堆栈为空，则表示表达式是平衡的，否则表示表达式不平衡。

N:B当我们检查左括号或不使用isItLeftBracket(ch)时我们检查映射是否包含键因为所有键都在左括号中就像我们检查右括号一样这里使用isItRightBracket(ch)我们检查映射是否包含值因为所有map的值都在右括号中

package com.codewithsouma.stack;
    
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Stack;
    
    public class BalancedExpressionUsingMap {
        private final Map<Character,Character> map;
    
        public BalancedExpressionUsingMap() {
            this.map = new HashMap<>();
            map.put('(',')');
            map.put('[',']');
            map.put('<','>');
            map.put('{','}');
        }
    
        public boolean isBalanced(String expression){
            Stack<Character> leftBracketContainer = new Stack<>();
            char [] arrayOfCharacter = expression.toCharArray();
            for (char ch : arrayOfCharacter) {
                if(isItLeftBracket(ch))
                    leftBracketContainer.push(ch);
                else if(isItRightBracket(ch)){
                    if(leftBracketContainer.isEmpty()) return false;
    
                    char leftBracket = leftBracketContainer.pop();
                    char oppositeBracket = getOppositeBracket(leftBracket);
                    if (oppositeBracket != ch) return false;
                }
            }
    
            return leftBracketContainer.isEmpty();
        }
    
        private char getOppositeBracket(char leftBracket) {
            return map.get(leftBracket);
        }
    
        private boolean isItRightBracket(char ch) {
            return map.containsValue(ch);
        }
    
        private boolean isItLeftBracket(char ch) {
            return map.containsKey(ch);
        }
    }

Answer 7

不需要为分隔符分配堆栈，可以使用递归函数跳过平衡子表达式，在不匹配时返回NULL:

#include <stdio.h>
const char *check(const char *s, char open) {
    while (*s) {
        switch (*s++) {
        case ')': return (open == '(') ? s : NULL;
        case ']': return (open == '[') ? s : NULL;
        case '}': return (open == '{') ? s : NULL;
        case '>': return (open == '<') ? s : NULL;
        case '(':
        case '[':
        case '{':
        case '<':
            s = check(s, s[-1]);
            if (s == NULL)
                return NULL;
            break;
        }
    }
    if (open) {
        /* closing delimiter not found */
        return NULL;
    }
    return s;
}
void test(const char *s) {
    printf("%s -> %sn", s, check(s, 0) ? "Balanced" : "Unbalanced");
}
int main() {
    test("((A+B)+(C+D))");
    test("((A+B))+(C+D))");
    test("((A+B)+(C+D)");
    test("((A+B)+(C+D})");
    return 0;
}

输出:

((A+B)+(C+D)) -> Balanced
((A+B))+(C+D)) -> Unbalanced
((A+B)+(C+D) -> Unbalanced
((A+B)+(C+D}) -> Unbalanced

请注意，与您的断言相反，((A+B))+(C+D))是不平衡的。