C++ If-else if statement executing when wrong conditions are met

Question

I am trying to solve this problem that finds if an expression has matching grouping symbols or not:

Write a program that takes as input an arithmetic expression. The program outputs whether the expression contains matching grouping symbols. For example, the arithmetic expressions {25 + (3 - 6) * 8} and 7 + 8 * 2 contains matching grouping symbols. However, the expression 5 + {13 + 7) / 8 -2 *9 does not contains matching grouping symbols.

So far, i have written this code using stacks and strings.

#include <iostream>
#include <string>
#include <stack>

using namespace std;

void matchingSymbol(string);

int main()
{
    matchingSymbol("{25+(3-6)*8}"); //match
    matchingSymbol("7+(8*2");       //no match

    string input;
    cout << "Enter an arithemtic to check for matching grouping symbols: ";
    cin >> skipws >> input;
    matchingSymbol(input);

}

void matchingSymbol(string arithInput)
{
    stack<char> tempStr;

    for (int i = 0; i < arithInput.length(); i++) {
        if (arithInput.at(i) == '{' || arithInput.at(i) == '(' || arithInput.at(i) == '[') {
            tempStr.push(arithInput.at(i));
        }
        else if (!tempStr.empty() && (arithInput.at(i) == '}' && tempStr.top() == '{' || arithInput.at(i) == ')' && tempStr.top() == '(' || arithInput.at(i) == ']' && tempStr.top() == '[') ){
            cout << "Popped for arithInput: " << arithInput.at(i) << " and tempStr: " << tempStr.top() << "\n";
            tempStr.pop();
        }
    }

    if (tempStr.empty()) {
        cout << arithInput << " --> " << "Groupings matched.\n";
    }
    else {
        cout << arithInput << " --> " << "Groupings not matched.\n";
    }

}

Output:

    Popped for arithInput: ) and tempStr: (
    Popped for arithInput: } and tempStr: {
    {25+(3-6)*8} --> Groupings matched.
    7+(8*2 --> Groupings not matched.
    Enter an arithemtic to check for matching grouping symbols: 1+[1}]
    Popped for arithInput: ] and tempStr: [
    1+[1}] --> Groupings matched.

I am running into an issue where input such as 1+[1}] would pass as grouped, but obviously isn't. I have a condition in the else if statement that says: I pop from tempStr if and only if a closing character is the complementary to the top element in the opening character stack. In the case of 1+[1}], i read the character } and check that the topmost in stack is [. The program shouldn't pop from tempStr yet it is.

Note: an empty tempStr stack means that the expression is grouped properly.

I have tried to change my conditions and refactor them and track all the variables but I can't see the flaw in my logic. It would be great if you can help me pinpoint why input such as 1+[1}] is passing as grouped, yet it isn't.

so far, this is the most efficient logic i have come up with:

pseudocode else if (stack not empty AND (closing symbol is read AND top on stack is its complementary))  {
pop stack
}

Start using a debugger. [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jason, Mar 30 '23 at 07:21
More parens in `(arithInput.at(i) == '}' && tempStr.top() == '{' || arithInput.at(i) == ')' && tempStr.top() == '(' || arithInput.at(i) == ']' && tempStr.top() == '[') )` and store `arithInput.at(i)` in a string tomake it much more readable ! — John3136, Mar 30 '23 at 07:22
@John3136 adding more parens did not help and ended in the same logic. — aboudi, Mar 30 '23 at 07:27
You need `(c =='}' && top =='{) || (c ==']' && top =='[')` ... — John3136, Mar 30 '23 at 07:37
`&&` has higher precedence than `||` (both are left-to-right associative) so for conditions `a`, `b`, `c`, and `d`, the expression `a && b || c && d` is equivalent to `(a && b) || (c && d)`. A common beginner (and even non-beginner) mistake is to believe either that (1) `||` has higher precedence so `a && b || c && d` is equivalent to `a && (b || c) && d` or (2) evaluation happens left to right, so is equivalent to `((a && b) || c) && d`. It is likely you're making at least one of these mistakes. Practically, it is often better to liberally use `()` to make your intent explicit. — Peter, Mar 30 '23 at 09:00
This doesn't address the question, but all those calls to `arithInput.at(i)` are wasting time. You **know** that `i` is a valid index into the array, because the `for` loop ensures that. You don't need to test it seven more times. Just use `arithInput[i]`. — Pete Becker, Mar 30 '23 at 13:13

score 3 · Accepted Answer · edited Mar 30 '23 at 10:26

You're missing a condition. You have the conditions to handle what happens if your missing a parenthesis but not how to handle an extra one. If you modify your loop like so:

for (int i = 0; i < arithInput.length(); i++) {
    auto character(arithInput.at(i));
    std::string top;
    if (!tempStr.empty())
        top = tempStr.top();

    if (arithInput.at(i) == '{' || arithInput.at(i) == '(' || arithInput.at(i) == '[')) {
        tempStr.push(arithInput.at(i));
    }
    else if (!tempStr.empty() && (arithInput.at(i) == '}' && tempStr.top() == '{' || arithInput.at(i) == ')' && tempStr.top() == '(' || arithInput.at(i) == ']' && tempStr.top() == '[') ){
        std::cout << "Popped for arithInput: " << arithInput.at(i) << " and tempStr: " << tempStr.top() << "\n";
        tempStr.pop();
    }
    else if (!tempStr.empty() && (arithInput.at(i) == '}' && tempStr.top() != '{' || arithInput.at(i) == ')' && tempStr.top() != '(' || arithInput.at(i) == ']' && tempStr.top() != '[')) {
        break;
    }
}

then you should be able to pick up the case you identified. The last condition specifies that if you encounter a closing parenthesis type that is not at the top of the stack, then you have a not-matching scenario.

This worked great. I see how i need to check for the if not case for top. Thank you. I am running into another issue where 1+(1)] is counting as grouped, but I will try to figure that you and probably add a check for that. i have to add a condition for when the stack is empty yet i still need to see any closing brackets with no openers. I will work on that. If you have any input, it's much appreciated. Thank you! — aboudi, Mar 30 '23 at 07:53
Added this line to check when stack is empty and everything works perfectly and checks for lone closers or openers at the end. Thank you! ```else if (tempStr.empty() && (arithInput.at(i) == '}' || arithInput.at(i) == ')' || arithInput.at(i) == ']')) { tempStr.push('x'); break; } ``` — aboudi, Mar 30 '23 at 08:11

score 1 · Answer 2 · answered Mar 30 '23 at 09:09

You have already gotten a good answer, but I just want to chime in with a few ways to improve and simplify it.

First, use a range-for loop instead of the counting for.

for (int i = 0; i < arithInput.length(); i++) {
    ...
    if (arithInput.at(i) == '{'

can be simplified to:

for (const char in: arithInput) {
    ...
    if (in == '{'

This alone can make all your if conditions much shorter and easy to read (if only because they fit on the screen).

Secondly, if you rethink your algorithm a bit, then it becomes possible to collapse a lot of the conditions. As it is you push the opening symbol you find onto the stack, and this means that you later has to do a lot of work to make sure that the closing symbol you find matches that particular type of opening. If you add a small complication at the start, and push the closer you expect instead, then your program can be simplified to this:

void matchingSymbol(std::string arithInput)
{
    std::stack<char> tempStr;

    for (const char in : arithInput)
    {
        // Instead of pushing the start, push what you need to match
        if (in == '{')
            tempStr.push('}');
        else if (in == '(')
            tempStr.push(')');
        else if (in == '[')
            tempStr.push(']');

        // Now you only need to look for a closing symbol
        else if (in == '}' ||
                 in == ')' ||
                 in == ']')
        {
            // And then check that it matches what is expected
            if (!tempStr.empty() && in == tempStr.top())
                tempStr.pop();
            else
            {
                tempStr.push('x');
                break;
            }
        }
    }

    if (tempStr.empty())
        std::cout << arithInput << " --> Groupings matched.\n";
    else
        std::cout << arithInput << " --> Groupings not matched.\n";
}

score 0 · Answer 3 · answered Mar 30 '23 at 08:17

Final revision of working implementation:

#include <iostream>
#include <string>
#include <stack>

using namespace std;

void matchingSymbol(string);

int main()
{
    matchingSymbol("{25+(3-6)*8}"); //match
    matchingSymbol("7+(8*2");       //no match

    string input;
    cout << "Enter an arithemtic to check for matching grouping symbols: ";
    cin >> skipws >> input;
    matchingSymbol(input);

}

void matchingSymbol(string arithInput)
{
    stack<char> tempStr;

    for (int i = 0; i < arithInput.length(); i++) {
        if (arithInput.at(i) == '{' || arithInput.at(i) == '(' || arithInput.at(i) == '[') {
            tempStr.push(arithInput.at(i));
        }
        else if (!tempStr.empty() && (arithInput.at(i) == '}' && tempStr.top() == '{' || arithInput.at(i) == ')' && tempStr.top() == '(' || arithInput.at(i) == ']' && tempStr.top() == '[')) {
            cout << "Popped for arithInput: " << arithInput.at(i) << " and tempStr: " << tempStr.top() << "\n";
            tempStr.pop();
        }
        else if (!tempStr.empty() && (arithInput.at(i) == '}' && tempStr.top() != '{' || arithInput.at(i) == ')' && tempStr.top() != '(' || arithInput.at(i) == ']' && tempStr.top() != '[')) {
            break;
        }
        else if (tempStr.empty() && (arithInput.at(i) == '}' || arithInput.at(i) == ')' || arithInput.at(i) == ']')) {
            tempStr.push('x'); //forces the stack to be not empty --> unmatched.
            break;
        }
    }

    if (tempStr.empty()) {
        cout << arithInput << " --> " << "Groupings matched.\n";
    }
    else {
        cout << arithInput << " --> " << "Groupings not matched.\n";
    }
} //thank you kate.

The answer looks fine, But a little explanation on why the code is working will be appreciated. — SARAN SURYA, Apr 04 '23 at 11:33

C++ If-else if statement executing when wrong conditions are met

3 Answers3