'cpp parse/explode expression into expression without brackets

I'm trying to build a "parser" in C++, that expands/explodes a formula into the equivalent without brackets, but im super stuck. A hint in the right direction would be super cool!

Example input:

1: "a and (b or c)"
2: "a and (b or (c and d))"

Desired output:

1: "a and b or a and c"
2: "a and b or a and c and d"

Evaluation the formulas is already done. But transforming the formula is getting me really frustrated. How would you solve this problem?

Thank you in advance!

Update: Thank you for the reply HolyBlackCat!

While searching for a solution I encountered the shunting-yard algorithm aswell. The following code is an implementation of that, and returns the infix notation correctly.

/* C++ implementation to convert
infix expression to postfix*/

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

// Function to return precedence of operators
int prec(char c)
{
    if (c == '^')
        return 3;
    else if (c == '&' || c == '*')
        return 2;
    else if (c == '+' || c == '-')
        return 1;
    else
        return -1;
}

// Convert infix expression to postfix expression
void infixToPostfix(string s)
{

    stack<char> st; // C++ built in stack
    string result;

    for (int i = 0; i < s.length(); i++)
    {
        char c = s[i];

        // If the scanned character is
        // an operand, add it to output string.
        if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'))
            result += c;

        // If the scanned character is an
        // ‘(‘, push it to the stack.
        else if (c == '(')
            st.push('(');

        // If the scanned character is an ‘)’,
        // pop and to output string from the stack
        // until an ‘(‘ is encountered.
        else if (c == ')')
        {
            while (st.top() != '(')
            {
                result += st.top();
                st.pop();
            }
            st.pop();
        }

        // If an operator is scanned
        else
        {
            while (!st.empty() && prec(s[i]) <= prec(st.top()))
            {
                if (c == '^' && st.top() == '^')
                    break;
                else
                {
                    result += st.top();
                    st.pop();
                }
            }
            st.push(c);
        }
    }

    // Pop all the remaining elements from the stack
    while (!st.empty())
    {
        result += st.top();
        st.pop();
    }

    cout << result << endl;
}

int main()
{
    string exp = "a*(c+b);";
    infixToPostfix(exp);
    return 0;
}

Outputs: acb+*

But still, I foresee how to turn it back into postfix notation with "exploded" parenthesis. Any push in the right direction would be awesome!



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source