Checking an arithmetic string brackets symmerty in best way

Question

I want to check if a given string like this:

(a[i]+{-1}*(8-9))

is valid

Valid means:

([]{}()) 

which is ok, and not Valid would be:

{([[}))

I'm trying to do this via stacks.
First stack extract any bracket of these 3 brackets and reverse push it. Second stack push it once again so if I have:

(   [   ]   {   }   (   )   )

First stack gets:

)   ]   }   )

and Second stack gets:

)   }   ]   )

Now Comes the logic part.

I've found a solution which was really really Ugly. What is the ideal? (and please do not make me post my solution since it is working, yet it is just messy and crappy and far away of "ideal")

Anyway, here is my arithmetric string and 2 stacks:

    public static string aritmethic { get; } = "( a[i]+{-1}*(8-9) )";
    Stack<char> original = new Stack<char>();
    Stack<char> temp = new Stack<char>();

Here is the First stack reverse push:

    public void PushToOriginal()
    {
        for (int i = 0; i < aritmethic.Length; i++)
        {
            if ((aritmethic[i] == '{'))
            {
                original.Push('}');
            }
            else if (aritmethic[i] == '[')
            {
                original.Push(']');
            }
            else if (aritmethic[i] == '(')
            {
                original.Push(')');
            }
        }
    }

The Second stack push:

    public void PushToTemp()
    {
        for (int i = 0; i < original.Count; i++)
        {
            temp.Push(original.Pop());
        }
    }

And now I need a decent logic behind this:

    public void Checker()
    {
        //Logic here 
        /*
        if (temp.Peek() == ....) 
        temp.Pop();
        *May cause an error  
        */
            if (temp.Count == 0)
                Console.WriteLine("Aritmethic Matches!");
            else
                Console.WriteLine("Aritmethic does not Match!!");
        }
    }

Hope I was clear enough about my question. Thx! BTW, I'm really fresh to CSharp so no harsh on me !

Answer 1

You can do all this quite simply using a single stack and a single pass through the input string:

var openers = "([{";
var closers = ")]}";
var brackets = new Stack<char>();
for (int i = 0; i != s.Length; ++i) {
    if (openers.Contains(s[i]))
        brackets.Push(s[i]);
    else if (closers.Contains(s[i])) {
        var opener = openers[closers.IndexOf(s[i])];
        if (brackets.Count == 0 || brackets.Peek() != opener)
            Console.WriteLine("Mismatched '{0}' at {1}", s[i], i);
        else
            brackets.Pop();
    }
}
if (brackets.Count != 0)
    Console.WriteLine("Unmatched '{0}'", brackets.Peek());

This works because when you encounter an opening bracket, the next thing you expect is a matching closing bracket (or another opening bracket that creates a nested scope). So the code pushes a new state onto the stack for each opening bracket, and when it encounters a closing bracket, it pops that state (checking that they match).

Answer 2

static void Main(String[] args)
{
    string input = "{()}";
    bool success = true;
    HashSet<char> openBrackets = new HashSet<char>() { '(', '{', '[' };
    HashSet<char> closeBrackets = new HashSet<char>() { ')', '}', ']' };
    Stack<char> mystack = new Stack<char>();
    for (int i = 0; i < input.Length; i++)
    {
        if (openBrackets.Contains(input[i]))
            mystack.Push(input[i]);
        else if (closeBrackets.Contains(input[i])){
            if(mystack.Count == 0)
            {
                success = false;
                break;
            }
            if (input[i] == '}' && mystack.Peek() == '{')
                    mystack.Pop();
            else if (input[i] == ')' && mystack.Peek() == '(')
                    mystack.Pop();
            else if (input[i] == ']' && mystack.Peek() == '[')
                    mystack.Pop();
            else
            {
                success = false;
                break;
            }
        }


    }

    if (mystack.Count == 0 && success)
        Console.WriteLine("Correct Input");
    else Console.WriteLine("Incorrect input");

    Console.ReadKey();
}

Algorithm: 1. Create a new stack!! 2. When you encounter an opening bracket, push it on the stack. 3. When you encounter a closing bracket, check it the current element on the top of the stack is a corresponding bracket of the closing bracket. If it is, then pop the top element of the stack. 4. Finally check if the remaining elements in your stack is zero or not!