Programme C++ pour vérifier si les ()s, {}s et []s sont équilibrés dans une chaîne de caractères.

Question

Voici donc mon problème :

Je suis censé écrire un programme c++ qui vérifie qu'une chaîne de caractères est équilibrée. Jusqu'à présent, j'ai réussi à faire fonctionner le code pour m'assurer qu'elle a le même nombre de ('s et de ) (de même que de ['s et de {'s). Le problème est que cela fonctionne pour presque tout, mais pas pour les chaînes de caractères où les {, les ( et les [ sont tous mélangés.

Par exemple : "{ { [ ( ) ] } ( ) }" revient équilibré (vrai) comme il se doit. Cependant, "{ ( [ ] } } )" revient vrai, mais il ne devrait pas.

Quelles sont les idées dans la logique et/ou le code qui permettraient de vérifier s'ils sont hors d'usage ?

Merci pour toute aide !

Au cas où cela vous aiderait, voici mon code :

bool ExpressionManager::isBalanced(string expression)
{
//remove whitespace
string edited;
for(int i = 0; i < expression.length(); i++)
{
    if(expression[i] == ' ')
    {
        continue;
    }
    else
    {
        edited += expression[i];
    }
}
expression = edited;

//set up brckets 
string brackets;

for(int i = 0; i < expression.length(); i++)
{
    if (expression.at(i)=='(')
    {
        brackets += expression.at(i);
    }
    if (expression.at(i)=='[')
    {
        brackets += expression.at(i);
    }
    if (expression.at(i)=='{')
    {
        brackets += expression.at(i);
    }
    if (expression.at(i)=='}')
    {
        brackets += expression.at(i);
    }
    if (expression.at(i)==']')
    {
        brackets += expression.at(i);
    }
    if (expression.at(i)==')')
    {
        brackets += expression.at(i);
    }
}

int parenbal = 0;
int brackbal = 0;
int mustachebal = 0;

    for (int i = 0; i<(brackets.size());i++)
    {

        if(brackets[i]=='(')
            parenbal++;
        if(brackets[i]=='[')
            brackbal++;
        if(brackets[i]=='{')
            mustachebal++;

        if(brackets[i]==')')
            parenbal--;
        if(brackets[i]==']')
            brackbal--;
        if(brackets[i]=='}')
            mustachebal--;
    }

    bool isbalanced = false;

    if ((mustachebal==0)&&(brackbal==0)&&(parenbal==0))
    {
        isbalanced = true;
    }

    //check for brackets mixed up with other stuff.

return isbalanced;
}

Answer 1

Si vous employez un Pile pour stocker ces jetons, alors vous cherchez toujours la contrepartie de fermeture correspondant à celle du haut de la pile ou un jeton ouvert.

Le flux serait le suivant

• Si le jeton est un jeton ouvert, poussez-le sur la pile.
• Si le jeton est un jeton fermé, vérifiez si le sommet de la pile est le jeton ouvert correspondant. Si c'est le cas, il faut sortir la pile comme vous l'avez trouvée équilibrée. Si ce n'est pas le cas, c'est une erreur.

Answer 2

Ça ressemble plus à un devoir à la maison. Je commenterai donc en conséquence et vous permettrai d'apprendre certaines choses.

1. Initialisez toujours vos variables. Les chaînes de caractères ne sont pas initialisées dans votre code.
2. Vous n'itérez pas sur la chaîne trois fois, vous ne pouvez vérifier la chaîne qu'une seule fois.
3. Utilisez la structure if-else if-else au lieu de la structure if-if-if.
4. Toujours utiliser des crochets
5. Soyez cohérent dans votre utilisation, utilisez soit at() soit [], mais ne les mélangez pas dans le code.

Answer 3

//this code may help you check string for balanced brackets with no
//repeated brackets,paranthesis or braces (e.g. [2*{3/(1+2)}].Note: no repeatance of
//brackets
#include <iostream.h>
#include <conio.h>
#include "IntStack.h"
#include <stdio.h>
void main(void)
{
    char bracket[20];
    gets (bracket);
    char arr[6];
    int i=0;
    while(i<20)
    {
        switch(bracket[i])
            {
                case '[':
                {
                    arr[0]=1;
                    break;
                }
                case '{':
                {
                    arr[1]=2;
                    break;
                }
                case '(':
                {
                    arr[2]=3;
                    break;
                }
                case ')':
                {
                    arr[3]=3;
                    break;
                }
                case '}':
                {
                    arr[4]=2;
                    break;
                }
                case ']':
                {
                    arr[5]=1;
                    break;
                }
                default:
                    cout<<"";
        }
        i++;
    }
    if(arr[3]==arr[2])
        cout<<"";
    else
        cout<<" ) or ( is missing "<<endl;

    if(arr[1]==arr[4])
        cout<<"";
    else
        cout<<" } or { is missing "<<endl;

    if(arr[5]==arr[0])
        cout<<"";
    else
        cout<<" ] or [ is missing"<<endl;
}

Answer 4

void check_brackets (string bituy) 
{
    int flag = 1

    int count[6] = {0, 0, 0, 0, 0, 0};
    stack<char> barstack;

    for (int i = 0; i < bituy.length(); i++)
    {
        if (bituy[i] == '{')
            count[0]++;
        else if (bituy[i] == '}')
            count[1]++;
        else if (bituy[i] == '(')
            count[2]++;
        else if (bituy[i] == ')')
            count[3]++;
        else if (bituy[i] == '[')
            count[4]++;
        else if (bituy[i] == ']')
            count[5]++;
    }

    for (int i = 0; i < 6; i += 2)
    {
        if (count[i] != count[i+1])
        {
            cout << "Wrong Syntax!" << endl;
            flag = 0;
            break;
        }
    }

    if (flag)
    {
        for (int i = 0; i < bituy.length(); i++)
        {
            if (bituy[i] == '{' || bituy[i] == '(' || bituy[i] == '[')
                barstack.push(bituy[i]);
            else
            {
                if ((barstack.top() == '{' && bituy[i] == '}') || (barstack.top() == '(' && bituy[i] == ')') || (barstack.top() == '[' && bituy[i] == ']'))
                    barstack.pop();
                else
                {
                    cout << "Wrong Syntax!" << endl;
                    flag = 0;
                    break;
                }
            }
        }
    }

    if (flag)
        cout << "No Errors!" << endl;

}

Answer 5

#include<bits/stdc++.h>
using namespace std;

bool isBalance(char n[],int size){
    int i,count=0;
    //int size=strlen(n);
    for(i=0;i<size;i++){
        if(n[i]=='{'||n[i]=='['||n[i]=='('){
            count ++;
           }
           else if(n[i]=='}'||n[i]==']'||n[i]==')'){
            count --;
           }
           else return -1;
    }
    if(count==0)
        return true;
    else
        return false;
}
int main(){
    char n[1000];
    gets(n);
    int size=strlen(n);
    bool result=isBalance(n,size);
    if(result==true)
        cout<<"Balance";
    else
        cout<<"Not Balance";
    return 0;
}