Output an Integer with Comma Every 3 Digits

Output an integer with comma, for example 1234567, will be "1,234,567"

C语言: 高亮代码由发芽网提供

01 void convert_number(char *str, char *out)
02 {
03         long number = atol(str);
04         if(number < 1000){
05                 strcpy(out, str);
06                 return;
07         }
08 
09 
10         long x = number;
11         long y = 1;
12 
13         while (x > 1000)
14         {
15                 y = y * 1000;
16                 x = x / 1000;
17         }
18 
19         char tmp[4];
20         x = number;
21         while (x > 1000)
22         {
23                 int value = x / y;
24 
25                 if (value < 10 && x != number)
26                         sprintf(tmp, "00%d", value);
27                 else if (value < 100 && x != number)
28                         sprintf(tmp, "0%d", value);
29                 else
30                         sprintf(tmp, "%d", value);
31                 strcat(out, tmp);
32                 strcat(out, ",");
33                 x = x % y;
34                 y = y / 1000;
35         }
36 
37         sprintf(tmp, "%ld", x);
38         strcat(out, tmp);
39 }

Reverse a String, Rotate a String and Reverse a Sentence

Implement 3 functions using C
1. Reverse a string:
    input: "abcdef"
    output: "fedcba"

2. Rotate a string to right by k place
    input: "abcdefg", 2
    output "cdefgab"

3. Reverse a sentence
    input: "This is a test."
    output: "test. a is This"

C语言: reverseString

01 #include<stdio.h>
02 
03 void reverse(char *str, int start, int end)
04 {
05      while(start<end)
06      {
07          char temp=str[start];
08          str[start++]=str[end];
09          str[end--]=temp;        
10      }
11 }
12 
13 void rotate(char *p, int k)
14 {
15      if(p==NULL)
16          return;
17      int len=strlen(p);
18      reverse(p,0,k-1);
19      reverse(p,k, len-1);
20      reverse(p,0,len-1);
21 }
22 
23 void reverseSentence(char *str)
24 {
25      int len=strlen(str);
26      reverse(str,0,len-1);
27      int start;
28      int end=0;
29      while(end<len)
30      {
31          if(str[end]!=' ')
32          {
33              start=end;
34              while(end<len && str[end]!=' ')
35              {
36                  end++;
37              }
38              end--;
39              reverse(str,start,end);
40          }
41          end++;      
42      }  
43 }
44 
45 int main()
46 {
47     char str[]="abcdefg";
48     printf("Before rotation: %s\n", str);
49     int len=strlen(str);
50   
51     rotate(str,2);
52     printf("After rotation: %s\n", str);
53   
54     char sentence[]="This is a test.";
55     reverseSentence(sentence);
56     printf("%s\n",sentence);  
57   
58     printf("Press any key to continue...");      
59     getch();
60     return 0;
61 }

Evaluate Reverse Polish Notation

An expresion in Reverse Polish Notation (RPN) is written such that each binary operator is placed after its operands. For example, the RPN 2 3 + will produce the sum of 2 and 3, namely 5.

Given a RPN expression consisting operands and binary operators + - * /, evaluate it.

For example,

["4", "1", "+", "2", "*"] = (4 + 1) * 2 = 10

["5", "8", "4", "/", "+"] = 5 + (8 / 4) = 7

Solution: use a stack. Keep pushing numbers into the stack, until you meet an operator. Pop two numbers from the stack, apply the operation, and push the result to stack. Using C language, you have to implement the stack yourself.

C语言: ReversePolish

01 #include<stdio.h>
02 #define STACK_SIZE 1000
03 
04 int stack[STACK_SIZE];
05 int stack_top=0;
06 void push(int value)
07 {
08      if(stack_top==STACK_SIZE) {
09          printf("stack overflow!");
10      }        
11      stack[stack_top++]=value;
12 }
13 
14 int pop()
15 {
16     if(stack_top==0) {
17         printf("stack is empty!");
18     }
19     return stack[--stack_top];  
20 }
21 
22 int isOperator(char *str)
23 {
24      char *p=str;
25      if(*p=='+' || *p=='-' || *p=='*' || *p=='/')
26      {
27          return 1;
28      }
29      else
30          return 0;
31 }
32 int main(int argc, char *argv[])
33 {
34     int i;  
35     for( i=1;i<argc;i++)
36     {
37         if(!isOperator(argv[i]))
38         {
39             push(atoi(argv[i]));
40         }
41         else
42         {
43             int op2=pop();
44             int op1=pop();
45             int value;
46             if(argv[i][0]=='+')
47             {
48                 value=op1+op2;
49             }
50             else if(argv[i][0]=='-')
51             {
52                  value=op1-op2;
53             }
54           
55             else if(argv[i][0]=='*')
56             {
57                  value=op1*op2;
58              }
59           
60              else if(argv[i][0]=='/')
61              {
62                  value=op1/op2;
63              }
64             push(value);          
65         }      
66     }
67     int result=pop();
68     printf("%d\n",result);
69   
70     printf("Press any key to continue...");
71     getch();
72     return 0;
73 }

Implementation of getline, atoi and itoa

In this blog, I introduce some implementation of the std functions in C.

getline(): read a line from user input.

C语言: getline

01 int getline(char *str, int lim)

02 {

03     char c;

04     char *p=str;    

05     while(--lim>0 && (c=getchar())!=EOF && c!='\n')

06     {

07         *p++=c;

08     }

09     *p='\0';

10     return p-str;    

11 }

atoi(): convert the character string representation of a number to the integer representation. Remember the sign, and remember to skip the spaces in front of the string.

C语言: atoi

01 int atoi(char *p)

02 {  

03     int n=0, sign;

04     //skip spaces

05     while(*p==' ')

06         p++;  

07     //find the sign

08     sign=(*p=='-')?-1:1;    

09     //skip the sign

10     if(*p=='-'||*p=='+')

11         p++;

12     //calculate the value    

13     while((*p-'0')>=0&&(*p-'0')<=9)

14     {

15         n=10*n+(*p-'0');

16         p++;

17     }

18     return sign*n;

19 }

itoa(): the opposite of atoi(),convert the integer representation of a number to its character string representation. It's a little more tricky than atoi. You need to start from the beginning of the number. Get the last digit of a number is easy, we just mod 10. How to get the digit at the very beginning of a number? We need to know how many digits this number have first. I use length to represent it. To get the length, you need to keep multipling 10 (line 12 - 17). The very beginning digit is obtained from dividing the number by length, and the number becomes itself mod length. Then you shrink length by 1 less digit. For example, you have a number 123, length is 100. you divide it by 100, and you get 1. Then your length becomes 10, and your number becomes 23. Then you divide 23 by 10, you get 2. (line 20 - 26)In the end you have a remaining number 3, just append it to the end of the string (line 28 - 29). 

C语言: itoa

01 char *itoa(int num, char *str)
02 {
03      //remember the beginning of the string
04     char *start=str;  
05     if(num<0)
06     {
07         *str++='-';      
08         num=-num;
09     }
10     int x=num;
11     //length is the number of digits
12     int length=1;
13     while(x>10)
14     {
15         length*=10;
16         x/=10;
17     }
18     int digit;
19     //get the digit from high to low
20     while(length>=10)
21     {
22         digit=num/length;
23         *str++=digit+'0';
24         num=num%length;
25         length=length/10;      
26     }
27     //last digit
28     if(num>=0)
29         *str++=num+'0';
30     //end of string    
31     *str='\0';
32     //return the beginning of the string    
33     return start;
34 }

C Code to Count the Number of Words in a String

Count the number of words in a string, where a word is defined to be a contiguous sequence of non-space characters.

eg, "Hello, my name is John." -> 5

Hint: Take account for extra spaces at the start and end of the string, and there might be more than multiple spaces between words.

C语言: CountNumOfWords

01 int countNumWords(char *str)
02 {
03     char *p=str;
04     if(*p=='\0')
05     {
06         return 0;
07     }
08     int len=strlen(str);
09     char *q=p+len-1;
10     int count=1;
11     while(*p==' ') p++;
12     while(*q==' ') q--;
13     if(p>=q)
14         return 0;
15     while(p<q && *p!='\0')
16     {
17         p++;
18         if(*p==' ')
19         {
20            while(*p==' ')
21            {
22                p++;
23            }
24            count++;
25         }
26     }
27     return count;
28 }