C++ Help needed

Discussion in 'OT Technology' started by mrburner, Feb 4, 2004.

  1. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    yes i posted something about a C program a few days ago but it turns out that has been significantly moved back...however, i have this program due this friday and have no idea where to start...it deals with finite automata

    the pdf is only avaliable on campus so hopefully copy and paste formatting from acrobat is the same...any help would be greatly appreciated

    CS253
    Programming Project 1
    1. Write a short C++ program called even.cpp that decides the set of strings that are both of even
    length and contain at least one vowel (vowels are aeiou). To make this problem a little more
    interesting, your program can only use cin and variables of type bool and char (no arrays, no
    strings, no pointers). Furthermore, you can’t use recursion. Thus, you will have to read the input
    one character at a time (since you would need an array of characters to store the whole input
    string at once; there is a get() method on cin that reads just one character). Your program will read
    its string as the first line on standard input. If your program accepts the string, it should simply
    print “[accept]” and exit. If it does not accept the input, it should print “[reject]” and exit.
    The point of this problem is to recognize the similarity between finite automata and a very
    restricted programming language. Without arrays, pointers and recursion, your program can only
    use a finite amount of memory. This is exactly the type of memory restriction that finite automata
    operate under.
    2. For this problem, you are to write a program called NFA.cpp that simulates an NFA. Your
    program will read an NFA description in the input format given below. It will accept (print out
    “[accept]”) if and only if a given input string is in the language of its given NFA. Otherwise, your
    program will print out “[reject]” and exit. Here, you get to use the full C++ language (you don’t
    have to program under the restrictions of problem 2).
    Your program will read its NFA description from a file and will read the input string for that NFA
    from standard input. The following example is a sample NFA description for your program. Each
    line starting with trans describes a transition of the automaton. The first value after trans gives the
    state (number) the transition is from, the next value gives the input symbol for which the
    transition will be taken and the third value gives the destination state for the transition. Thus, the
    fifth input line says that there is a transition from state 1 to state 2 on input symbol b. The input
    symbols will always be in the range a ... z. Also, since the automaton is nondeterministic, there
    may be more than one transition from the same state on the same input symbol. You may assume
    that the NFA has no more than 20 states and no more than 50 transitions.
    Lines that start with the word final indicate final (accepting) states for the automaton. The number
    after the keyword final gives the state that is an accepting state. For automata that have more than
    one final state, there may be more than one final line. All final lines will come after all trans lines.
    If the automaton description does not define a transition for every input symbol from every state,
    you can assume that the undefined transitions don’t lead to accepting states. You should also
    assume that state 0 is always the start state.
    trans 0 a 0
    trans 0 b 0
    trans 0 c 0
    trans 0 a 1
    trans 1 b 2
    trans 2 c 3
    trans 0 b 4
    trans 4 b 5
    trans 5 b 3
    trans 3 a 3
    trans 3 b 3
    final 3
    The input string for the NFA will be read from standard input. The string will be given on a line
    by itself and will consist of only characters from a ... z.
    3. Write a C++ program named all pairs.cpp that enumerates the set of all pairs of natural numbers
    (1,2 ...). For this program you can, of course, use the full C++ language (no restrictions on types
    or recursion). Also, you should pretend that the C++ long type supports unbounded magnitude.
    Thus, a loop like the following will never terminate:
    long i = 1;
    while ( i > 0 )
    i++;
    To enumerate pairs, just print out lines like the following
    (1,1)
    (2,1)
    (1,2)
    (3,1)
    (2,2)
    (1,3)
    ...
    which uses the diagonalization technique found on page 162 of the text. If we place the pairs of
    natural numbers in an infinite 2-D matrix, then we want to enumerate the pairs along the diagonals.
    This allows all pairs to be enumerated instead of producing an infinite sequence of pairs that start
    with 1, i.e., (1,1) (1,2), (1,3) …
     
  2. XtremelyCanadian

    XtremelyCanadian I play hockey.....EH

    Joined:
    Jan 4, 2002
    Messages:
    1,801
    Likes Received:
    0
    Location:
    Edmonton,Canada
    For the first one, i think there is a len() function in C++, so you could just modulus the output of len() to find if its even or not. Then just figure out some algorithm to go through each character and then "if" it to see if it matches up with any vowels. Sorry havent done C++ in a long time so i cant give you any code, but the first question shouldn't be too hard.

    EDIT: sorry its not len() its str.size() and i think its the stdlib.h file that you have to import.
     
  3. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    i know how to read a line of input at a time, but how do i go character by character? i could do this if we were allowed to use arrays or pointers or recursion

    i'm stuck on number 1 for now...so far i am opening a file but don't know how to read 1 character at a time
     
  4. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    k here is what i have for the first program so far

    #include <iostream.h>
    #include <fstream.h>
    #include <iomanip.h>
    #include <stdlib.h>

    int main()
    {
    char file_name[300]; //giving the input and output files

    ifstream input_file;

    //user input for the input file
    cout << "Please enter the name and path of the input file: ";
    cin >> file_name;
    input_file.open(file_name);

    if(!input_file.is_open())
    {
    cout << "There was an error opening your file.";
    }
    else
    {
    char ch;
    int i = 0;
    int b = 0;
    while(input_file.get(ch))
    {
    i += 1;
    if(ch == "a" || ch == "e" || ch == "i" || ch == "o" || ch == "u")
    {
    b += 1;
    }
    }
    if(i % 2 == 0 && b > 0)
    {
    cout << "[accept]" << endl;
    }
    else
    {
    cout << "[reject]" << endl;
    }

    }

    now my only problem is on this line
    if(ch == "a" || ch == "e" || ch == "i" || ch == "o" || ch == "u")

    because it is telling me illegal operand (||)
    i'm sure you see what i'm trying to do with this...can you tell me why its not working or what i can do to get around this? thanks
     
  5. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    k well i am still stuck on number 1 but i started on number 2 and i have no idea how to read the input...like i understand how to read input, but the input is "trans 0 a 0"...so how can i just read the first 5 letters first to find out if it is "trans" or "final" and then how can i read the rest seperately to do something with it?

    i will try to start coding the rest of that but i am really having a hard time figuring that out...i have looked at as many online resources as i could find but i still can't figure out how to seperate that single line of input

    any help at all would be greatly appreciated
     
  6. sam758

    sam758 OT Supporter

    Joined:
    Aug 26, 2003
    Messages:
    901
    Likes Received:
    0
    it's prolly too late, but for the first part, the reason why you're getting that error is because you're trying to compare a char with a string ("a"), you need ch == 'a'.
    also b should really be boolean, you don't want an integer since it will wrap around when it reaches its max value. good luck on your project.
     

Share This Page