Thread: <<simple stack program questions

I am having alot of trouble figuring out this program...any help would be greatly appreciated...

Write a program that prompts for a file name and then reads the file to
check for balanced curly braces, {}; parentheses, (); and square brackets,
[]. Use a stack to store the most recent unmatched left symbol. The program
should ignore character that is not a parenthesis, curly brace, or square
bracket. Note that proper nesting is required. For instance, [a(b]c) is
invalid.

Code:

Output
1. {{a+5}-7*[1-{4/2}]}/{2*(3-6)} Valid
2. {(a+5)-7*[1-{4/2}])/{2*(3-6)} Invalid

I know how to read chars from the file...etc. i'm just having problems figuring out how to go about solving this....i cant seem to figure out a proper algorithm that'll do what the problem is asking.....help!!

whenever you encouter a OPEN bracket, brace or whatever you PUSH it onto the stack maybe together with some additional information (like the position where that bracket, brace, etc was found)

when you find a CLOSE bracket thingy you check the top of the stack wheter this it is legal:
if you find a { and the top of the stack symbol is a } then you simply pop the stack.
in case you find a [ and the top of the stack symbol is a } (somethat thats NOT ]) then thats an error and you display some error message

like:

Code:

struct OpenInfo {
  OpenInfo(char symbol, int position) {this->symbol = symbol; this->position = position; }

  char symbol; // either {, ( or [
  int position; // where in the input stream that symbol was encountered
};

std::stack< OpenInfo > stack;

while(not end of input) {
  switch(current_input_symbol) {
     case '[': stack.push(OpenInfo('[', current_position)); break;
     case '{': stack.push(OpenInfo('}', current_position)); break;
     case '(': stack.push(OpenInfo(')', current_position)); break;
     case ']': if(stack.top().symbol != '[') std::cout << "error at " << stack.top.position << "\n"; break;
     case '}': if(stack.top().symbol != '{') std::cout << "error at " << stack.top.position << "\n"; break;
     case ')': if(stack.top().symbol != '(') std::cout << "error at " << stack.top.position << "\n"; break;
  }
}

Ok, this is pretty much what i have so far....it works on some cases...but when i try to implement other strings, it gives me a windows error..no compile errors...here is the code i have so far...

Code:

#include <stack>
#include <fstream>
#include <iostream>


using namespace std;

int main()
{
	
	stack<char> charStack;
	
	char cChar;
		
	ifstream inFile;
	
	
	inFile.open("infile.txt");  
	
	if(!inFile)                
	{
		cout<<"Input file does not exist."<<endl;
		return 1;
	}
	
		inFile>>cChar;
	
	while(inFile)
	{
				
		if (cChar == '{' || cChar == '[' || cChar == '(')
		{
			charStack.push(cChar);
		}
		
		else
		{
			if (charStack.top() == '(')
			{
				if (cChar == ')')
				{
				charStack.pop();
				}
			}
			else if (charStack.top() == '[')
			{
				if(cChar == ']')
				{
					charStack.pop();
				}
			}
			else if (charStack.top() == '{')
			{
				if(cChar == '}')
				{
					charStack.pop();
				}
			}
		}
		

		inFile>>cChar;
	}

	if(charStack.empty()) 
	{
		cout<<endl<<"Valid"<<endl;
	}
	
	else 
	{
		cout<<endl<<"Invalid"<<endl;
	}
	

	cin.get();

return 0;

}

when i use these input files, I get a valid output....

Code:

input:
{(a+5)-7*[1-{4/2}])/{2*(3-6)} //invalid

input:
(((({[]})()()))){} //valid

input:
{{()}  //invalid

and i get windows errors on the following

Code:

input:
{()[()]}} 

input:
{{a+5}-7*[1-{4/2}]}/{2*(3-6)}

HELP!!!

> if (charStack.top() == '(')
You also need to check .empty() before trying to test the top

Simply follow through your code with a simple input of
)
to see what I mean.