Stack implementation to check C++ parentheses

Question

I'm trying to implement a stack to check if a file has balanced (), [], and {}. The program is supposed to take in a file and check if it is balanced and return a boolean. When I run the program it only works for the last parentheses in the file. How can I change the code to make it work for parentheses before the last pair. The input file is just a simple c file.

Side question:

If I wanted to make this program work with an html file do I just have to change (), [], {} with the html tags?

This is the code I have

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <stack>
#include <string>

using namespace std;

bool balanced(string A[], int n)
{
    int i;
    stack <string> a;

    for (i = 0; i < n; i++) {
        if (A[i] == "(" || A[i] == "{" || A[i] == "["){
            a.push(A[i]);
        } else
        if (A[i] == ")" || A[i] == "}" || A[i] == "]") {
            if (a.empty()) {
                return false;
            } else {
                a.pop();
                return true;
            }
        }
    }
}

int main()
{
    ifstream infile;
    infile.open ("Text.txt");
    string A[1000];

    int i = 0;
    int n = (sizeof(A) / sizeof(*A));

    while (!infile.eof()) {
        getline(infile, A[i], '\n');
        i++;
    }

    bool out;
    out = balanced(A, n);

    if (out == true) {
        cout << "legal";
    } else {
        cout << "illegal";
    }

    return 0;
}

`while (!infile.eof())` is one of the great statements of DOOM. It looks so logical, but [it's also dead wrong](https://stackoverflow.com/questions/5605125/why-is-iostreameof-inside-a-loop-condition-considered-wrong). Note how it checks for the end of the file BEFORE reading the data. What if the next data in the file IS the end of the file? Ka-blammo. You want `while (getline(infile, A[i], '\n'))` — user4581301, Apr 04 '18 at 01:59
Your program is not correct. It will report that something like this: `{)` is balanced, when it isn't. You should be checking whether the top-of-stack character has a brace type that matches the closing brace character. — PaulMcKenzie, Apr 04 '18 at 02:03
Extra credit. Write the program so it is correct (no false positives or negatives), and returns balanced == true when given its own source file as input. I did it. It was fun. I think I might post it as an answer. R. Ren would know better than to crib from it. He would be found out without doubt. What say, R? Should I post it? — Jive Dadson, Apr 04 '18 at 05:43
You read the file in a while loop getting one at each turn. So at the end you have the last line AND then you checked if it is balanced... Read the file char by char and push/pop accordingly — Jean-Baptiste Yunès, Apr 04 '18 at 08:17
@R.Ren, your idea is not correct. you need to do something different. — Eziz Durdyyev, Apr 04 '18 at 09:56

score 0 · Answer 1 · answered Apr 04 '18 at 01:44

0

In your file, the last line is a single closing brace }. isn't it? You're not checking characters, you only check lines, and when you look for an opening parentesis, you expect it to be the only character on the line. So, for your program to successfully count all the parentheses, the input file needs to look like

int main
(
    int argc, char **argv
)
{

and so forth.

You need to not only iterate though A in your balanced(), but also iterate though every its element. For instance,

for(std::size_t i{}; i < n; ++i) {
    for(char c: A[i]) {
        if(c == '(' || c == '[' || c == '{') {

answered Apr 04 '18 at 01:44

bipll

11,747
1
18
32

Still, it is not giving the correct result for `({)}`. – Eziz Durdyyev Apr 04 '18 at 09:53
Sure, I only suggested to fix one problem and probably let OP try to deal with others. – bipll Apr 04 '18 at 11:42

score 0 · Accepted Answer · answered Apr 04 '18 at 10:00

Your solution will work for only one kind of parentheses even if you fix your bugs as @bipll suggested. This is the full explanation of the solution that will solve your problem. And here is C++ code:

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

// function to check if paranthesis are balanced
bool areParanthesisBalanced(char expr[])
{
    stack<char> s;
    char a, b, c;

    // Traversing the Expression
    for (int i=0; i<strlen(expr); i++)
    {
        if (expr[i]=='('||expr[i]=='['||expr[i]=='{')
        {
            // Push the element in the stack
            s.push(expr[i]);
        }
        else
        {
            switch (expr[i])
            {
            case ')':

                // Store the top element in a
                a = s.top();
                s.pop();
                if (a=='{'||a=='[')
                    cout<<"Not Balancedn";
                break;
            case '}':

                // Store the top element in b
                b = s.top();
                s.pop();
                if (b=='('||b=='[')
                    cout<<"Not Balancedn";
                break;
            case ']':

                // Store the top element in c
                c=s.top();
                s.pop();
                if (c=='('||c=='{')
                    cout<<"Not Balancedn";
                break;
            }
        }
    }

    // Check Empty Stack
    if (s.empty())
        return true;
    else
        return false;
}

// Driver program to test above function
int main()
{
    char expr[]="{()}[]";

    if(areParanthesisBalanced(expr))
        cout<<"Balanced";
    else
        cout<<"Not Balanced";
    return 0;
}

Jive Dadson · Answer 3 · 2018-04-04T08:14:56.380

-1

I could not resist doing a sort of puzzle version. The challenge I set, just for fun, was to write a correct program per the assignment, which is itself balanced. That pretty much rules out braces in literals like "[" or,

if (A[i] == "(" || A[i] == "{" || A[i] == "["){
    a.push(A[i]);
}

For fun, I feed its source code through itself, and it returns OK==true. Of course it works for any file.

Take note of how reading the file and filtering out the uninteresting characters is relegated to a function, "get".

#include <stack>
#include <string>
#include <fstream>
#include <cassert>

static std::string chars{ "(){}[]" };

static char get(std::ifstream &in) {
    char nxt;
    while (in >> nxt) {
        if (std::string::npos != chars.find(nxt)) {
            return nxt;
        }
    }
    return 0;
}
int main(int argc, char* argv[]) {
    std::ifstream in(argv[1]);
    std::stack<char> stk;
    bool OK = true;
    for (char nxt = get(in); nxt; nxt = get(in)) {
        auto pos = chars.find(nxt);
        if (pos % 2) {
            if (stk.empty() || stk.top() != chars[pos-1]) {
                OK = false; break;
            } else {
                stk.pop();
            }
        } else {
            stk.push(nxt);
        }
    }
    return OK;
}

edited Apr 04 '18 at 08:14

answered Apr 04 '18 at 06:31

Jive Dadson

16,680
9
52
65

Why is this 'extra credit'? If it is correct, it is correct for any input, not just its own source code. – user207421 Apr 04 '18 at 06:43
@EJP - It is correct for all input. (Empty and non-existent files are considered balanced.) – Jive Dadson Apr 04 '18 at 06:58
@EJP - I think I wrote the description badly. I edited it. – Jive Dadson Apr 04 '18 at 07:07
A correct program cannot have unbalanced parentheses. Your point escapes me. This is an answer to a question, but it isn't an extra-credit answer in any way. – user207421 Apr 04 '18 at 07:40
@EJP - You are imagining a C++ tokenizer. I am only considering reading one char at a time. A correct program can contain those bracket symbols within single or double quotes. In fact, the OP's program fragment does. It is not balanced. – Jive Dadson Apr 04 '18 at 07:47
@EJP - It's a puzzle. For fun. I hope you have plenty. – Jive Dadson Apr 04 '18 at 07:49

Stack implementation to check C++ parentheses

3 Answers3