<<simple stack program questions

This is a discussion on <<simple stack program questions within the C++ Programming forums, part of the General Programming Boards category; I am having alot of trouble figuring out this program...any help would be greatly appreciated... Write a program that prompts ...

  1. #1
    Registered User
    Join Date
    Apr 2004
    Posts
    5

    <<simple program using Stacks - 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!!
    Last edited by rdt253; 03-25-2005 at 04:54 PM.

  2. #2
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    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;
      }
    }
    signature under construction

  3. #3
    Registered User
    Join Date
    Apr 2004
    Posts
    5
    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!!!
    Last edited by rdt253; 03-25-2005 at 08:12 PM.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BOOKKEEPING PROGRAM, need help!
    By yabud in forum C Programming
    Replies: 3
    Last Post: 11-16-2006, 10:17 PM
  2. Stringy Sums
    By bumfluff in forum C++ Programming
    Replies: 14
    Last Post: 05-15-2006, 01:52 AM
  3. Character stack ADT program
    By alice in forum C Programming
    Replies: 1
    Last Post: 07-05-2004, 04:30 AM
  4. Stack Program Here
    By Troll_King in forum C Programming
    Replies: 7
    Last Post: 10-15-2001, 05:36 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21