C/C++ Programming Questions Not Worth Their Own Thread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > C/C++ Programming Questions Not Worth Their Own Thread

«‹›641 »

Nalin: Sep 29, 2007; Hair Elf

icantfindaname posted:

Is there any easy way to concatenate a character to a string in C? Specifically, take a character out of another string, iterating through with a for loop. I tried strcat but apparently it needs to be a constant char for that to work. The program is supposed to check whether a string is a palindrome.
code:
for (i = StringLength (InputLine) - 1; i >= 0; i--) {
	if (!(StringEqual (CharToString(InputLine[i]), " "))) {
		//insert concat function here
	}
}

When dealing with string functions in C, you have to remember that your destination character array has to have been allocated with enough characters to do whatever it is you are trying to do. If your destination character array is too small, you will have to create a new array and copy your old string into it.

That said, all you are trying to do is check if a string is a palindrome? You shouldn't need to do any concatenation at all.

code:

// Create a pointer to the beginning...
const char* ptr_to_start = InputLine;

// ...and the end of the string.  Subtract 1 so we aren't pointing to the terminating NULL.
const char* ptr_to_end = InputLine + strlen(InputLine) - 1;

// We start our loop.
// Check if the two pointers are equal.  If this is a palindrome, they should be.
// Also, add a check for the middle of the string.
while ((*ptr_to_start == *ptr_to_end) && (ptr_to_end - ptr_to_start > 1))
{
  // Move both pointers towards the middle.
  ++ptr_to_start;
  --ptr_to_end;
}

// If both pointers reached the middle, and they are equal, we have a palindrome!
if ((*ptr_to_start == *ptr_to_end) && (ptr_to_end - ptr_to_start <= 1))
  // success!  Is a palindrome.
else
  // failure!  Is not a palindrome.

Nalin fucked around with this message at 20:34 on Feb 23, 2011

# ? Feb 23, 2011 05:34

Adbot: ADBOT LOVES YOU

# ? Jun 5, 2024 00:23

icantfindaname: Jul 1, 2008

Alright, thanks

# ? Feb 23, 2011 05:45

Standish: May 21, 2001

icantfindaname posted:

Is there any easy way to concatenate a character to a string in C? Specifically, take a character out of another string, iterating through with a for loop. I tried strcat but apparently it needs to be a constant char for that to work

strcat() takes a pointer to a const char, not a const char. There is no library function to append a single char to a string. You would need to create a char[] consisting of the char followed by a terminating null and pass that to strcat(). That said you should do it the way Nalin explained.

Also Nalin, looks like you need a tweak: http://codepad.org/zgM8s6YW

Standish fucked around with this message at 19:52 on Feb 23, 2011

# ? Feb 23, 2011 19:27

Nalin: Sep 29, 2007; Hair Elf

Standish posted:

Also Nalin, looks like you need a tweak: http://codepad.org/zgM8s6YW

Well, that's embarrassing. I edited my post with a fix.

# ? Feb 23, 2011 20:34

Manic Mongoose: Aug 5, 2010

Hi, I'm currently working on a project and am really trying to wrap my head around the construction of a grep; where inputting a pattern like

./rgrep pattern

would result in search for files with the similar pattern.

I've been given the skeleton code and the only thing I really need to work on is the pattern matching but I'm really at a loss at where to start.

Here's an excerpt from the assignment:

Your assignment is to complete the implementation of rgrep, our simplified, restricted grep.
rgrep is "restricted" in the sense that the patterns it matches only support a few regular operators
(the easier ones). The way rgrep is used is that a pattern is simplified on the command line.
rgrep then reads lines from its standard input and prints them out on its standard output if and
only if the pattern "matches" the line. For example, we can use rgrep to search for lines that
contain text file names that are 3-5 characters long (plus the extension) with the following:
$ cat testin #so you can see what lines are in the file
this file is fine.txt
the filename s.txt is too short
and reallylong.txt is too long
but super.txt is just right!
$ ./rgrep ' ....?.?\.txt' < testin #note the space before the first .
this file is fine.txt
but super.txt is just right!

I'm not asking for answers but kind of guidance. I'm also not sure what the cat does.

sucking at everything tends to suck and I'd really like to understand this. :[

# ? Feb 24, 2011 10:11

nielsm: Jun 1, 2009

First, the cat command is here just used to print the contents of a file. (Cat is for concatenate, write contents of input files serially on stdout.)

I'm not sure what level of guidance you're otherwise asking for. You'd probably want to construct a DFM (deterministic finite-state machine) that matches the input pattern, but it really depends on the class you're taking. (Are you learning C++ or are you learning text processing?)

# ? Feb 24, 2011 10:45

Manic Mongoose: Aug 5, 2010

Well right now I'm learning C++ but it's basically revolving around computer organization and design.

Here's the skeleton code. with the pattern match empty.

code:

#include <stdio.h>
#include <stdlib.h>

#define MAXLINE 256

char *progn;

void usage(void)
{
  fprintf(stderr,"Usage: %s pattern\n",progn);
}

int pattern_match(char *pattern, char *str)
{
  // magic
}

int main(int argc, char **argv)
{
  char line[MAXLINE];
  char *pattern;
  progn = argv[0];
  
  if(argc!=2) {
    usage();
    return EXIT_FAILURE;
  }
  pattern = argv[1];
  
  while(!feof(stdin) && !ferror(stdin)) {
    if(!fgets(line,sizeof(line),stdin)) {
      break;
    }
    if(pattern_match(pattern,line)) {
      printf("%s",line);
    }
  }
  if(ferror(stdin)) {
    perror(progn);
    return EXIT_FAILURE;
  }
  return EXIT_SUCCESS;
}

and here's a continuation of the project explanation:

What's going on here? rgrep was given the pattern " ....?.?\.txt"; it printed only the lines
from its standard input that matched this pattern. How can you tell if a line matches the pattern?
A line matches a pattern iff the pattern "appears" somewhere inside the line. In the absense
of any special operators, seeing if a line matches a pattern reduces to seeing if the pattern occurs
as a substring anywhere in the line. So for most characters, their meaning in a pattern is just to
match themselves in the target string. However, there are a few special characters you must

implement:
. (period) Matches any character.
? (question mark) The preceding character may or may not appear in the line.
\ (backslash) "Escapes" the following character, nullifying any special meaning it has

As for guidance, mostly where, or how to start. Sorry for the inconvenience.

Manic Mongoose fucked around with this message at 19:12 on Feb 24, 2011

# ? Feb 24, 2011 18:15

Gothmog1065: May 14, 2009

Okay, another stupid question.

I'm trying to create a "madlibs" type program. someone mentioned it to me and it makes me feel good knowing I can actually possibly do something on my own. It should be exceptionally simple, ask for a word, store it, ask for the next word, so on. I know I'm doing something completely wrong. It asks for the first word, takes the imput then closes. Here's the snippet of the code:

code:

#include <iostream>
using namespace std;

main()
{
      char noun1, pnoun1, noun2, pnoun2, place, adjective;
      cout << "Please enter a noun:";
      cin >> noun1;
      cout << "\nNoun in";
      cout << "\nPlease enter a plural noun:";
      cin >> pnoun1;
      cout << "\nNoun: " << noun1 << " Plural noun: " << pnoun1;
      
      // Rest of the program to go in later. 

      char response;
      cin >> response;
      return 0;
}

It's not stopping at the cin >> response;. Is this something simple or am I missing some major concept somewhere?

# ? Feb 24, 2011 18:37

roomforthetuna: Mar 22, 2005; I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

Gothmog1065 posted:

It's not stopping at the cin >> response;. Is this something simple or am I missing some major concept somewhere?

You're getting single chars from cin instead of strings.

# ? Feb 24, 2011 18:43

Vanadium: Jan 8, 2005

A char is a singly byte. When you say cin >> noun1 you read a single byte into noun1 and leave the rest of the word or whatever in a buffer for the next cin >>. Since the next one still has something to read, it will not stop to wait for input.

You will probably want to replace all your uses of char with std::string and also #include <string> to begin with.

# ? Feb 24, 2011 18:44

Gothmog1065: May 14, 2009

roomforthetuna posted:

You're getting single chars from cin instead of strings.

Thanks you two, but that leads me to this question, if you don't clear the buffer/put all the characters into some sort of variable, it'll just roll through all your cin's?

# ? Feb 24, 2011 19:08

pseudorandom name: May 6, 2007

Yes, console input is buffered by default.

# ? Feb 24, 2011 19:11

Vanadium: Jan 8, 2005

Yeah, reading from std::cin basically blocks until you press return or whatever, then it keeps all that in its buffer and only blocks and reads input again once that buffer has been used up.

You can use std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); to ignore input data up to the next newline, which works well if you know that there is a newline at the end of every input. Or you can read whole lines at a time using std::string someString; std::getline(std::cin, someString); which reads up to and discards the next newline.

# ? Feb 24, 2011 19:13

roomforthetuna: Mar 22, 2005; I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

Gothmog1065 posted:

Thanks you two, but that leads me to this question, if you don't clear the buffer/put all the characters into some sort of variable, it'll just roll through all your cin's?

cin >> mycharacter will read only one character and the rest of the buffer will remain.
cin >> mystring will read to... a space? a newline? I forget, but to some sort of delimeter, I expect you can change what it is, and the rest of the buffer will remain.

Whenever something remains in the buffer, it will roll over to the next "cin >>", so if you read a single character as you do, and you entered "foo(enter)", it would roll through four or five "cin >>" instances, reading one character each time. (Four or five because it depends whether your newlines are \n like unix or \r\n like windows.) And then the next "cin >> whatever" would block for more input.

# ? Feb 24, 2011 19:13

Gerblyn: Apr 4, 2007; "TO BATTLE!"; Fun Shoe

Manic Mongoose posted:

As for guidance, mostly where, or how to start. Sorry for the inconvenience.

It's kind of hard to answer your question, since I'm not entirely sure about your skill level with programming or how specific you want the guidance to be... But as for a general approach, you probably want to break the problem down into pieces:

1) Where do I put my code?

- According to your sample, in a function called "pattern_match" that takes two "const char*" arguments, one for the pattern to be found, the other for the line to search. The function should return a boolean value, true if the pattern has been found, false otherwise.

2) How do I recognize if the pattern has appeared in the line?

- You need a loop that can check a part of the string "line", and see if a consecutive string of characters matches their equivalents within "pattern".

3) How do I check the whole string for instances of the pattern?

- You need a loop that goes through every character in the string, and applies the loop from (2) to sub-strings that start with each character.

If you're not familiar with how strings in C work, the following C snippet demonstrates how you can compare two strings to see if they're the same:

code:


bool compare_strings(const char *string_one, const char *string_two)
{
  // Declare two character pointers that will move along the strings we want to compare
  const char *walker_one=string_one;
  const char *walker_two=string_two;

  // This loop will continue until our walker pointers reach the end of either string.
  // Strings in C end in a special character, '\0' (which is the same as 0 or NULL)
  // It will also end if "break" is called
  while(*walker_one!='\0' && *walker_two!='\0')
  {
    // If the character pointed at by the first walker isn't the same as the one
    // from the second pointer, then stop the loop early
    if (*walker_one!=*walker_two)
    {
      break;
    }

    // Move both walkers one stop along to the next characters in the string
    walker_one++;
    walker_two++;
  }

  // When we get here, we know that if we reached the end of both strings, they
  // must be the same, otherwise they must be different
  if (*walker_one=='\0' && *walker_two=='\0')
    return true;
  else
    return false;
}

I don't actually have a compiler on hand, so I haven't actually compiled/tested the above, but it should contain all the language elements you need to solve your pattern matching problem.

Gerblyn fucked around with this message at 19:26 on Feb 24, 2011

# ? Feb 24, 2011 19:19

Vanadium: Jan 8, 2005

roomforthetuna posted:

(Four or five because it depends whether your newlines are \n like unix or \r\n like windows.)

You cannot actually read whitespace into chars using operator>> because whitespace being the record separator, the istream just skips over it.

# ? Feb 24, 2011 19:21

roomforthetuna: Mar 22, 2005; I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

Vanadium posted:

You cannot actually read whitespace into chars using operator>> because whitespace being the record separator, the istream just skips over it.

Really? That's pretty lovely behaviour, I can't think of any situation where while reading single characters I'd want
"foo
bar
"
to read in identically to "foobar" without me deliberately making it so.

Anyway, if so, sorry about that, my mistake - I don't use streams because I don't like the way they try to help resulting in, apparently, unexpected behaviour exactly like this example. Hopefully the rest of the response still answers the question.

vvvv But I'd just end up using that way that syntactically resembles regular file-reads all the time, so I might as well just use regular C-style reads into buffers on the stack in the first place.

roomforthetuna fucked around with this message at 19:39 on Feb 24, 2011

# ? Feb 24, 2011 19:28

Vanadium: Jan 8, 2005

I figure at that point you would just use std::istream's get() member function, if not the underlying streambuf. :shobon:

# ? Feb 24, 2011 19:32

Gothmog1065: May 14, 2009

roomforthetuna posted:

Anyway, if so, sorry about that, my mistake - I don't use streams because I don't like the way they try to help resulting in, apparently, unexpected behaviour exactly like this example. Hopefully the rest of the response still answers the question.

Yeah, this is why I'm glad I have access to these forums, it helps to have something explained multiple ways.

# ? Feb 24, 2011 19:36

Manic Mongoose: Aug 5, 2010

Gerblyn, thanks for the help, it makes a lot of sense. I'm having trouble applying this to searching file names though. maybe if I were to look inside a file for comparisons. but file name search wise. I'm iffy still.

But the comparative code makes a lot of sense!

# ? Feb 24, 2011 21:27

Gerblyn: Apr 4, 2007; "TO BATTLE!"; Fun Shoe

Unless I'm missing something, the search for filenames thing is just to give an example of how your rgrep program could be used. So, if I have a text file that contains the following:

moose.txt
inflatable.jpg
hungry.avi
skips.txt
blobby.jpg

and I want to use the program to find all the txt files which have filenames 9 characters long, I can use the pattern: .....\.txt (i.e. 5 characters that are anything, followed by a full stop, then txt) to find them.

# ? Feb 24, 2011 23:02

Manic Mongoose: Aug 5, 2010

Alright. Got that and loaded the sample info accordingly, for now I'm just trying to have the program find a match and I'll implement the operators later.

So another question:

int pattern_match(char *pattern, char *str)
{
const char *read1 = pattern;
const char *read2 = str;

while(*read1 != '\0' && *read2 != '\0')
{
if(*read1 != *read2)
{
break;
}
read1++;
read2++;

I'm pretty much putting that sample code you gave me in because I understand it, I'm just having trouble connecting it to main though.

Does setting the pointers to pattern and str put them into an array? and as such when I increment them ++ am I going character by character? right now running this

code:

int pattern_match(char *pattern, char *str)
{
  const char *read1 = pattern;
  const char *read2 = str;
  
  while(*read1 != '\0' && *read2 != '\0')
  {
               if(*read1 != *read2)
               {
                        break;
               }
  read1++;
  read2++;
  }
  if(*read1 == '\0' && *read2 == '\0')
  {
           printf("%s\n", str);
           return 1;
  }
  else
      return 0;
}

gives me a hanging program, which is the same as if I had nothing in it.

I put

this file is fine.txt
the filename s.txt is too short
and reallylong.txt is too long
but super.txt is just right!

into a file called test.txt

and ran

./rgrep 'fine'

to see if I could get a match.

thanks for the help so far.

# ? Feb 25, 2011 01:11

roomforthetuna: Mar 22, 2005; I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

Your program needs the file as an input - it isn't told to load a file anywhere, so it's trying to match your pattern against console input (from the keyboard) rather than from a file.

In Unix, this is done like
./rgrep 'fine' <filename
or
cat filename | ./rgrep 'fine'

It's crazy that they have you trying to write a unix command line program without having told you how to use a unix command line.

Edit: (this is why it's "locking up", because it's waiting for input.)

roomforthetuna fucked around with this message at 03:27 on Feb 25, 2011

# ? Feb 25, 2011 03:12

A MIRACLE: Sep 17, 2007; All right. It's Saturday night; I have no date, a two-liter bottle of Shasta and my all-Rush mix-tape... Let's rock.

Manic Mongoose posted:

thanks for the help so far.

Hey, if you're program is hanging up, try compiling with -g option, then running your executable within gdb. When the program hangs up, start printing your variables (type p VARIABLE or p *VARIABLE), that might help you see where your problem is.

# ? Feb 25, 2011 03:13

Manic Mongoose: Aug 5, 2010

Ah now its working.

It was explained in the project pdf but not clearly enough for me.

So now I've got it returning the searched pattern if in the file there's a single word.

Such as in my
test.txt
is the word turkey.

if I ./rgrep turkey <test.txt
it'll work

however if I add any additional words to the line or lines under it it prints nothing.

I'm also trying to treat periods as any characters if for example
I put for the pattern '.....'

if I do something like

if(*read1== '.')
{
*read1++;
}

would that work?

# ? Feb 25, 2011 03:16

Nalin: Sep 29, 2007; Hair Elf

Manic Mongoose posted:

thanks for the help so far.

You know, I started to write out a description of an algorithm you could use before I realized how difficult this is going to be for you.

Take this as an example pattern:
....?x?ts

Based on the rules you gave, the following will match it:
eeeexts
eeexts
eeets

Once you start dealing with optional characters, it gets so much more difficult to design. You will need to try to pattern match against every combination of optional characters in your pattern. That means, you have to run your pattern match using the following patterns:
....xts
...xts
....ts
...ts

Testing against a simple pattern without any optional characters is easy. Just use two loops, like so:

code:

int pattern_match(char *pattern, char *str)
{
  // Loop through every character in the string.
  for (int i = 0; i <= strlen(str) - strlen(pattern); ++i)
  {
    // Search our pattern against our position.
    for (int j = 0; j < strlen(pattern); ++j)
    {
      bool escaped = false;

      // Do a test for \
      if (pattern[j] == '\\')
      {
        // Increment our position in our pattern so we test against
        // the actual character.  Also, we want to specify that escaped is true
        // so we don't try to interpret the . as an "any character" mark.
        ++j;
        escaped = true;
      }

      // Do a test for . if the . was not escaped.
      if (pattern[j] == '.' && !escaped)
        continue;

      // Check if our current position in the pattern matches our string.
      // If it is not set, break out of the loop and continue iterating along our string.
      if (pattern[j] != str[i + j])
        ..
    }

    // If we reached the end of our pattern without aborting early,
    // then we have a matching pattern!
    if (j >= strlen(pattern))
      return 1;
  }

  // Failure!
  return 0;
}

Unfortunately, I'm not aware of an easy algorithm that can handle optional characters.

# ? Feb 25, 2011 03:27

nielsm: Jun 1, 2009

I think the easiest way might be to do a recursive algorithm.

Pseudocode:

code:

partial_match (pattern, text):
	if pattern is empty:
		return true

	get first character in pattern
	if character is escape character (\):
		first character is next character in pattern
	else if next character in pattern is optional character marker (?):
		set optional match flag to true

	// see if current character matches
	set direct match flag to: match first character in pattern against first character in text

	// if this character doesn't match and it isn't optional, the match has failed
	// this should also fail when the end of input is reached and there is at least
	// one non-optional character left in the pattern
	if not direct match and not optional match:
		return false

	// the further result of the matching depends on whether
	// the rest of the string matches the rest of the pattern
	set result to: partial_match (pattern[except used characters], text[except first character])

	if optional match:
		// if this character was an optional one, also see whether the rest of the string
		// can match if the optional character isn't used
		boolean 'or' result with: partial_match (pattern[except used characters], text[entire input])

	return result


anywhere_match(pattern, text):
	while text is not empty:
		// test every position in text, whether the pattern matches starting there
		if partial_match(pattern, text):
			return true
		else:
			eat first character of text

	// all of the text was used up with no match
	return false

Seriously, this is a hard problem.

# ? Feb 25, 2011 03:54

Manic Mongoose: Aug 5, 2010

thanks alot you guys. I'm slowly getting there. I'm glad I'm at least understanding this.

# ? Feb 25, 2011 04:18

Nalin: Sep 29, 2007; Hair Elf

nielsm posted:

I think the easiest way might be to do a recursive algorithm.

Oh yeah, that would definitely work. If we find an optional character, we just recursively call our pattern_match function to match WITHOUT the character. This should take care of all cases.

EDIT: Working code.

Try to implement nielsm's solution first before messing with this:
http://pastebin.com/6wEgxkgJ

Nalin fucked around with this message at 09:04 on Feb 25, 2011

# ? Feb 25, 2011 04:19

nielsm: Jun 1, 2009

Nalin posted:

Oh yeah, that would definitely work. If we find an optional character, we just recursively call our pattern_match function to match WITHOUT the character. This should take care of all cases.
code:
int pattern_match(char *pattern, char *str)
{
  // Loop through every character in the string.
  for (int i = 0; i <= strlen(str) - strlen(pattern); ++i)
  {
    // Search our pattern against our position.
    for (int j = 0; j < strlen(pattern); ++j)
    {

That's bad, you can't use it recursively that way.
If you do this, any number of characters can appear between each character in the pattern.

Assuming the rest of your code is right (I didn't read it in detail), it would still allow the pattern "AB" to match "xxA__1234__Byy".
When the matching begins at position 3 in the input text, "A" from the pattern matches the first character in "A__1234__Byy". Then the pattern "B" is attempted matched against "__1234__Byy" which will also succeed because the same "match anywhere" algorithm is employed.

You need to have a partial_match function called by the pattern_match function, or if you don't want to have a helper function (by far the clearest) then keep a stack of your own inside the function.

Oh yeah, and don't ever use strlen() in a loop condition! Remember that strlen() is O(n) on the length of the string! The best way to loop over a string (in C) is the walking pointer method.

# ? Feb 25, 2011 04:47

Manic Mongoose: Aug 5, 2010

Hey Nalin I was wondering what does

// Check if our current position in the pattern matches our string.
// If it is not set, break out of the loop and continue iterating along our string.
if (pattern[j] != str[i + j])
..

this mean.

does the .. mean fill it in myself?

I tried setting a break and that just hangs it.

And I was talking with my TA

if I were to use for loops, I should set up the initial loops like this

code:

  int i,j;
  for(i = 0; i < strlen(str); i++)
  {
          for(j = 0; j < strlen(pattern); j++)
          {
            pattern[j] == str[i+k]
            k++;
            //fill in j ?\ . stuff

to handle the question mark is like

code:

if (pattern[j+1] == '?')
{
  j = j +2; //depends on for(j) or while
  k++;
}

else
{
j= j+2; //depends on for(j) or while
}
}

using the walker method was easier to keep track of in my mind where as trying these for loops usually get me all mixed up.

I'm not quite sure of the difference.

Manic Mongoose fucked around with this message at 06:50 on Feb 25, 2011

# ? Feb 25, 2011 06:38

Nalin: Sep 29, 2007; Hair Elf

nielsm posted:

That's bad, you can't use it recursively that way.
If you do this, any number of characters can appear between each character in the pattern.

Oh yeah, and don't ever use strlen() in a loop condition! Remember that strlen() is O(n) on the length of the string! The best way to loop over a string (in C) is the walking pointer method.

No, the code works. Well, it works now. There were some errors with it because I never tested it, but I updated my post with a working solution. And yeah, I know about not using strlen(). I just picked it because I figured it would be easier for him to understand.

Manic Mongoose posted:

Yeah, I had originally meant for you to write code for the blanks. There were some problems with my code (I never tested it), but I fixed them and edited my post with a working version.

If anybody else wants to try to solve it a different way, it would be interesting to see how you do it.

# ? Feb 25, 2011 08:01

nielsm: Jun 1, 2009

Nalin posted:

No, the code works. Well, it works now.

Actually no it doesn't. I just tried building it and it has exactly the problem I described.

code:

> rgrep-nalin.exe "ii" < rgrep-test.txt
this file is fine.txt
the filename s.txt is too short
and reallylong.txt is too long
but super.txt is just right!

All of the lines in the file have at least two "i"s, but none of them have two "i"s in succession.

Nalin posted:

If anybody else wants to try to solve it a different way, it would be interesting to see how you do it.

I implemented my algorithm from above almost verbatim:

code:

int partial_match(char *pattern, char *str)
{
	char matchchar;
	int optional_match;
	int matches_here;
	
	matchchar = pattern[0];
	
	if (matchchar == '\0')
	{
		/* empty pattern matches anything */
		return 1;
	}
	
	if (matchchar == '\\')
	{
		pattern++;
		if (pattern[0] == '\0')
			/* pattern ends with an escape character, invalid syntax, match fails */
			return 0;
		matchchar = pattern[0];
	}
	else if (matchchar == '.')
	{
		/* an unescaped dot is a wildcard, distinguish it from an escaped dot
		   by making a nul char mean wildcard */
		matchchar = '\0';
	}
	
	pattern++;
	
	if (pattern[0] == '?')
	{
		optional_match = 1;
		pattern++;
	}
	else
	{
		optional_match = 0;
	}
	
	if (!optional_match && str[0] == '\0')
	{
		/* end of input text but not of pattern, fails.
		   this check is needed because matchchar=='\0' is used for wildcard */
		return 0;
	}
	
	matches_here = (str[0] == matchchar || matchchar == '\0');
	
	if (optional_match)
	{
		/* either the current character matches and the rest of the pattern matches
		   the rest of the string,
		   or the current character is skipped and the rest of the pattern matches
		   the entire input string. */
		return (matches_here && partial_match(pattern, str+1))
		    || partial_match(pattern, str);
	}
	else
	{
		/* the current character has to match and the rest of the pattern must match
		   the rest of the string */
		return matches_here && partial_match(pattern, str+1);
	}
}

int pattern_match(char *pattern, char *str)
{
	/* try matching at every position in the string */
	/* left as an exercise to the reader */
	return 0;
}

I blanked out a little part to make it not a complete solution to the homework :rolleyes:

# ? Feb 25, 2011 08:18

Nalin: Sep 29, 2007; Hair Elf

nielsm posted:

Actually no it doesn't. I just tried building it and it has exactly the problem I described.
code:
> rgrep-nalin.exe "ii" < rgrep-test.txt
this file is fine.txt
the filename s.txt is too short
and reallylong.txt is too long
but super.txt is just right!
All of the lines in the file have at least two "i"s, but none of them have two "i"s in succession.

That's weird because I get:

code:

Testing pattern: ii
: Testing string: this file is fine.txt
:  - Failure
: Testing string: the filename s.txt is too short
:  - Failure
: Testing string: and reallylong.txt is too long
:  - Failure
: Testing string: but super.txt is just right!
:  - Failure

EDIT: My solution returns -1 on failure. Maybe that is the cause of the discrepancy?

Nalin fucked around with this message at 09:05 on Feb 25, 2011

# ? Feb 25, 2011 08:35

Manic Mongoose: Aug 5, 2010

thanks for the help guys. I'm reading over this stuff, making sense of it and will tackle it in the morning!

# ? Feb 25, 2011 10:41

nielsm: Jun 1, 2009

Nalin posted:

EDIT: My solution returns -1 on failure. Maybe that is the cause of the discrepancy?

I was simply inserting it into the skeleton program, assuming you were following the same API, so possibly yes.

# ? Feb 25, 2011 10:49

The1ManMoshPit: Apr 17, 2005

Compile the pattern to a DFA and then run the DFA on the input :coolfish:

# ? Feb 25, 2011 14:36

Deep Dish Fuckfest: Sep 6, 2006; Advanced
Computer Touching; Toilet Rascal

I've got a question about virtual inheritance. Suppose I have the following class hierarchy:

code:

class A {};

class B : virtual public A {};

class C : public B {};

class D : virtual public A {};

class E : public C, public D {};

If I compile this in Visual Studio, I end up with an object memory layout that looks something like this: {A*, B, C, A*, D, E, A}, with the leftmost entry having the lowest memory address and both virtual inheritance pointers pointing to the single A object. This is exactly what I was expecting.

However, if I change the hierarchy to

code:

class A {};

class B : public A {};

class C : virtual public B {};

class D : virtual public A {};

class E : public C, public D {};

then what I would expect to see is {B*, C, A*, D, E, A, B}, with both pointers pointing to the start of the A object. What I get, though, is something like {B*, C, A*, D, E, A, B, A}, with the B* pointer pointing to the first A and the A* pointing to the second A, which is not inheritance mechanism I was expecting.

At first glance, I can't really see anything that would be broken if the compiler did what I expected it to do, so basically I'm wondering if I just missed something and there's a good reason it's not handled that way, or if the standard just happens to forbid that.

# ? Feb 25, 2011 17:43

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

The rule is that virtual bases are uniqued in the complete object, but only with other virtual bases of the same type. So your complete object type there has (roughly) the structure:

code:

struct E_complete {
  struct E {
    struct C {
      void *vbptr;
    };
    struct D {
      void *vbptr;
    };
  };
  struct B {
    struct A {
    };
  };
  struct A {
  };
};

# ? Feb 25, 2011 19:12

Adbot: ADBOT LOVES YOU

# ? Jun 5, 2024 00:23

That Turkey Story: Mar 30, 2003

YeOldeButchere posted:

then what I would expect to see is {B*, C, A*, D, E, A, B}, with both pointers pointing to the start of the A object.

What I get, though, is something like {B*, C, A*, D, E, A, B, A}, with the B* pointer pointing to the first A and the A* pointing to the second A, which is not inheritance mechanism I was expecting.

Why exactly do you think there wouldn't be a second A? You didn't make it virtual. I'm not certain of the original rationale, but I don't think about it as a matter of "the standard could have just been written differently and it would have been fine". While it's true that a language could be defined to share A in scenarios similar to yours, I think there is a more subtle reason why that would be a bad idea.

Think about it like this. An instance of B has certain invariants. Inheritance here is non-virtual meaning that B knows it has its own base A and may rely on that fact to be certain its invariants aren't violated. An instance of D also has certain invariants, but inherits virtually from A. In E, we can't make the assumption that giving access to B's base A from D will not inadvertently allow D to violate B's invariants (or even vice-versa). If B inherited virtually from A, you'd be forming a contract that says "I know that other people share this base and that is okay". Without that virtual, E shouldn't allow D to point into B's A.

# ? Feb 25, 2011 19:37

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > C/C++ Programming Questions Not Worth Their Own Thread

«‹›641 »