Spiral Matrix Program in C - Zoho Interview Question - C Program to Read a Matrix in Spiral Order

A spiral matrix is a matrix (two dimensional array) in which the elements are stored in spiral manner. The order of accessing elements in the spiral matrix resembles a spiral. Actually it is a normal NxN two dimensional array. But instead of accessing elements row-wise or column-wise, we access them in spiral order. i.e, in a 3x3 matrix the order of retrieval of elements is spiral order is as follows:

(0,0)  (0,1)   (0,2)  (1,2)   (2,2)   (2,1)   (2,0)   (1,0)   (1,1)

The following picture shows a 4x4 spiral matrix:

A 4x4 Spiral matrix

Zoho, an IT company, asked an interview question which was to write a program to read a matrix spirally. In this post, we will answer this interview question  by zoho corporation. The only difference between spiral matrix and normal matrix is the order in which we store elements to matrix or access elements in matrix. The following is the C program to read a spiral matrix.

#include<stdio.h>
void main()
{
int a[10][10],o,cellcount,cc=0,c=0,i=0,j=0,g=1;
printf("\nEnter the order of spiral matrix: ");
scanf("%d",&o);
cellcount=o;
printf("\nEnter the elements:\n");
while(c<o*o)
    {
    cc=0;
    for(;cc<cellcount;j=j+g,cc++)
        scanf("%d",&a[i][j]);
    j=j-g;
    c+=cc;
    cc=0;
    i=i+g;
    cellcount--;
    if(c>=o*o)
        break;
    for(;cc<cellcount;i=i+g,cc++)
        scanf("%d",&a[i][j]);
    c+=cc;
    i=i-g;
    j=j-g;
    g*=-1;
    }
printf("\nThe spiral matrix is:");
for(i=0;i<o;i++)
    {
    printf("\n");
    for(j=0;j<o;j++)
        printf("%d\t",a[i][j]);
    }
}

The above program reads the matrix in spiral fashion and the displays the matrix in normal way. You can use this code not only to read and store the elements in matrix spirally but also to access the elements in the matrix in spiral order.

Related Posts:

C Compiler for Android Phones
C Program to Validate Sudoku - Check Correctness of Sudoku
C Program to Display Pascal's Triangle
C Program to Burst Consecutive Repetition of Numbers in Array
C Program to Display Strings Crossed
Tricky Interview Question - C Program to Rearrange an Array Without Using any Other Arrays
C Program to Convert Between Decimal, Binary, Hexadecimal and Octal Number Systems
C Program to Find Inverse of a Matrix
C Program to Find Largest Integer Formed Using Digits of Given Number
C Program to Count GrandChildren - Interview Question
How to get Random Number in C
C Program to Implement Circular Linked List
C Program to Swap Numbers with Bitwise Operators
C Program for Subtraction Without Using Minus Operator
C Program to Swap Numbers without Temporary Variable

Lexical Analyzer using C Program - Simulation of Lexical Analyzer in C Program

Finite Automata for Lexical analyzer (Click to enlarge)

The input to lexical analyzer is character stream. The character stream input is grouped into meaningful units called lexemes, which are then mapped into tokens, the latter constituting the output of the lexical analyzer. The lexical analyzer uses a symbol table. Each identifier, keyword and symbol are given unique id (symbol table id). The lexical analyzer is designed using finite automata. The finite automata for this program is added at the end of the post. The program takes a file input.c (in same file) as input. The input to a lexical analyzer is source string (source code as a long string). A sample input to the lexical analyzer is shown after this program.

Lexical Analyzer Program in C

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

//***********

struct token
{
char type[30];
char name[50];
int id;
}retToken;

//*******

struct symboltable
{
char type[30];
char name[50];
}st[60];

typedef struct token token;

char* sourcecode;
int lexbeg=0,fwdptr=0,state=0;
int symbolcount=0;
token newtoken;
int isexist=0,lineno=1;

//************

int indexof(char *subString,int fromIndex,char *MainString)
{
	int Mainlength,subLength,i,j,retIndex=-1;
	Mainlength=strlen(MainString);
	subLength=strlen(subString);
	if(Mainlength<1||subLength<1||Mainlength-fromIndex<subLength)
		return(-1);
	for(i=fromIndex;Mainlength-i>=subLength;i++)
		{
		if(*(MainString+i)==*(subString))
			{
			retIndex=i;
			for(j=0;j<subLength;j++)
				{
				if(*(MainString+i+j)!=*(subString+j))
					{
					retIndex=-1;
					break;
					}
				}
			if(retIndex!=-1)
				return retIndex;
			}
		}
	return (-1);
}

//************

char * subString(char *MainString,int fromIndex,int toIndex)
{
int Mainlength,j;
char *subStr;
Mainlength=strlen(MainString);
if(fromIndex<0||fromIndex>=Mainlength||toIndex<fromIndex||toIndex>=Mainlength)
	{
	printf("\nError in args: subString fn");
	return(NULL);
	}
subStr=(char *)malloc(1000*sizeof(char));
for(j=0;j<=toIndex-fromIndex;j++)
	*(subStr+j)=*(MainString+fromIndex+j);

*(subStr+j)='\0';
return(subStr);
}

//************

char nextchar()
{
fwdptr++;
return(sourcecode[fwdptr-1]);
}

//************

void retract(int n)
{
fwdptr-=n;
}

//************

int fail(char * msg)
	{
	printf("%s",msg);
	return(-1);
	}

//************

int installid(char *string)
{
int i;
for(i=0;i<symbolcount;i++)
{
if(strcmp(string,st[i].name)==0)
	return i;
}
strcpy(st[symbolcount].name,string);
strcpy(st[symbolcount].type,"identifier");
symbolcount++;
return(symbolcount-1);
}

//************

token getType(char *tok)
{
int i;
token tt;
for(i=0;i<symbolcount;i++)
	{
	if(strcmp(st[i].name,tok)==0)
		{
        strcpy(tt.type,st[i].type);
        strcpy(tt.name,st[i].name);
        tt.id=i;
		return(tt);
		}
	}

}

//************

int isSymbol(char c)
{
int i;
char syms[]={'.','<','>',',','{','}','(',')','#',';'};
for(i=0;i<10;i++)
{
if(c==syms[i])
	return(i+41);
}
return(0);
}

void nextToken()
{
char c;
char *temptok;
state=0;
while(*(sourcecode+fwdptr)!='\0'&&state!=-1)
{
switch(state)
	{
	case -1:return;
	case 0:c=nextchar();
		if(c==' '||c=='\t'||c=='\n')
			{
			state=0;
			lexbeg++;
			if(c=='\n')
				{
				lineno++;
				printf("\nline %d: ",lineno);
				}
			if(c=='\0')
				state=-1;
			}
		else if(c=='<')
			state=1;
		else if(c=='>')
			state=5;
		else if(c=='=')
			state=8;
		else if(isalpha(c))
			state=10;
		else if(isdigit(c))
			state=22;
		else if(isSymbol(c))
			state=24;
		else if(c=='+')
			state=12;
		else if(c=='-')
			state=15;
		else if(c=='*')
			state=18;
		else if(c=='/')
			state=19;
		else if(c=='%')
			state=20;
		else
			state=fail("unknown symbol encountered");
		break;
	case 1:c=nextchar();
		if(c=='=')
			state=2;
		else if(c=='>')
			state=3;
		else
			state=4;
		break;
	case 2:strcpy(retToken.type,"relop");
		strcpy(retToken.name,"LE");
		retToken.id=17;lexbeg=fwdptr;return;
	case 3:strcpy(retToken.type,"relop");retToken.id=18;
		strcpy(retToken.name,"NE");lexbeg=fwdptr;return;
	case 4:retract(1);
		strcpy(retToken.type,"relop");retToken.id=19;
		strcpy(retToken.name,"LT");lexbeg=fwdptr;return;
	case 5:c=nextchar();
		if(c=='=')
			state=6;
		else
			state=7;
		break;
	case 6:strcpy(retToken.type,"relop");retToken.id=20;
		strcpy(retToken.name,"GE");lexbeg=fwdptr;return;
	case 7:retract(1);
		strcpy(retToken.type,"relop");retToken.id=21;
		strcpy(retToken.name,"GT");lexbeg=fwdptr;return;
	case 8:c=nextchar();
		if(c=='=')
			state=9;
		else
			state=21;
		break;
	case 9:strcpy(retToken.type,"relop");retToken.id=22;
		strcpy(retToken.name,"EQ");lexbeg=fwdptr;return;
	case 10:c=nextchar();
		if(isalpha(c)||isdigit(c))
			state=10;
		else
			state=11;
		break;
	case 11:retract(1);
		temptok=subString(sourcecode,lexbeg,fwdptr-1);
		retToken.id=installid(temptok);
		retToken=getType(temptok);
		lexbeg=fwdptr;return;
	case 12:c=nextchar();
		if(c=='+')
			state=13;
		else
			state=14;
		break;
	case 13:strcpy(retToken.type,"arop");retToken.id=23;
		strcpy(retToken.name,"INC");lexbeg=fwdptr;return;
	case 14:retract(1);
		strcpy(retToken.type,"arop");retToken.id=24;
		strcpy(retToken.name,"PLU");lexbeg=fwdptr;return;
	case 15:c=nextchar();
		if(c=='-')
			state=16;
		else
			state=17;
		break;
	case 16:strcpy(retToken.type,"arop");retToken.id=25;
		strcpy(retToken.name,"DEC");lexbeg=fwdptr;return;
	case 17:retract(1);
		strcpy(retToken.type,"arop");retToken.id=26;
		strcpy(retToken.name,"MIN");lexbeg=fwdptr;return;
	case 18:strcpy(retToken.type,"arop");retToken.id=27;
		strcpy(retToken.name,"MUL");lexbeg=fwdptr;return;
	case 19:strcpy(retToken.type,"arop");retToken.id=28;
		strcpy(retToken.name,"DIV");lexbeg=fwdptr;return;
	case 20:strcpy(retToken.type,"arop");retToken.id=29;
		strcpy(retToken.name,"MOD");lexbeg=fwdptr;return;
	case 21:retract(1);retToken.id=30;
		strcpy(retToken.type,"arop");
		strcpy(retToken.name,"ASSIGN");lexbeg=fwdptr;return;
	case 22:c=nextchar();
		if(isdigit(c))
			state=22;
		else
			state=23;
		break;
	case 23:retract(1);retToken.id=41;
		strcpy(retToken.type,"Numeric constant");
		strcpy(retToken.name,subString(sourcecode,lexbeg,fwdptr-1));lexbeg=fwdptr;return;
	case 24:strcpy(retToken.type,"Reserved Symbol");retToken.id=isSymbol(c);
		strcpy(retToken.name,subString(sourcecode,lexbeg,fwdptr-1));lexbeg=fwdptr;return;

	}
}

}

//************

void regkeywords()
{
int i;
char keywords[][15]={"do","while","main","for","include","if","else","break","continue","int","char","float","double","void","return","switch","case"};
//17
char relop[][3]={"LE","NE","LT","GE","GT","EQ"};//17 to 22
char arop[][7]={"INC","PLU","DEC","MIN","MUL","DIV","MOD","ASSIGN"};//23 to 30
char syms[][2]={".","<",">",",","{","}","(",")","#",";"};//31 to 40

for(i=0;i<=16;i++)
{
strcpy(st[i].name,keywords[i]);
strcpy(st[i].type,"keyword");
}

for(i=17;i<=22;i++)
{
strcpy(st[i].name,relop[i-17]);
strcpy(st[i].type,"relop");
}

for(i=23;i<=30;i++)
{
strcpy(st[i].name,arop[i-23]);
strcpy(st[i].type,"arop");
}

for(i=31;i<41;i++)
{
strcpy(st[i].name,syms[i-31]);
strcpy(st[i].type,"Reserved Symbol");
}
strcpy(st[41].name,"NC");
strcpy(st[41].type,"Numeric Constant");
symbolcount=42;

}

//************

void main()
{
int i;
char c,*line;
FILE *input;
input=fopen("input.c","r");
i=0;
sourcecode=(char*)malloc(sizeof(char)*1200);
while((c=getc(input))!=EOF)
	{
	*(sourcecode+i)=c; i++;
	}
*(sourcecode+i)='\0';
regkeywords();
printf("\nline 1: ");
nextToken();
while(state!=-1)
{
printf("type: %s, name: %s, id= %d\n",retToken.type,retToken.name,retToken.id);
nextToken();
if(lexbeg>=strlen(sourcecode)||fwdptr>=strlen(sourcecode))
	state=-1;
}
printf("\nSymbol Table:\n");
for(i=0;i<=symbolcount;i++)
{
    printf("\nType: %s",st[i].type);
    printf("\tName: %s",st[i].name);
    printf("\tid=: %d",i);
}
}

Sample input (input.c) to the Lexical Analyzer

void main()
{
int a,b,c,d;
a=10;
b=30;
c=a+b;
d=a*b;
}

Operator Precedence Parsing Program in C - C Program to Implement Operator Precedence Parsing

Sample output - Click to enlarge

Parsing (Syntax analysis) is a topic in compiler construction. Operator Precedence parsing is one of i. For example, a sample input string to the operator precedence parser is i*(i+i).
the parsing techniques for ambiguous grammars. It solves the ambiguity by using operator precedence. In this post we will see a C program which implement operator precedence parsing to check the syntax for given input string. In input string (here a mathematical expression) the identifiers are denoted by

The grammar in this program is:

E  ->  i        / E*E       / E+E       / (E)       / E^E

i for identifier.
E is the start symbol.

#include<stdio.h>
#include<string.h>

char *input;
int i=0;
char lasthandle[6],stack[50],handles[][5]={")E(","E*E","E+E","i","E^E"};
//(E) becomes )E( when pushed to stack

int top=0,l;
char prec[9][9]={

                            /*input*/

            /*stack    +    -   *   /   ^   i   (   )   $  */

            /*  + */  '>', '>','<','<','<','<','<','>','>',

            /*  - */  '>', '>','<','<','<','<','<','>','>',

            /*  * */  '>', '>','>','>','<','<','<','>','>',

            /*  / */  '>', '>','>','>','<','<','<','>','>',

            /*  ^ */  '>', '>','>','>','<','<','<','>','>',

            /*  i */  '>', '>','>','>','>','e','e','>','>',

            /*  ( */  '<', '<','<','<','<','<','<','>','e',

            /*  ) */  '>', '>','>','>','>','e','e','>','>',

            /*  $ */  '<', '<','<','<','<','<','<','<','>',

                };

int getindex(char c)
{
switch(c)
    {
    case '+':return 0;
    case '-':return 1;
    case '*':return 2;
    case '/':return 3;
    case '^':return 4;
    case 'i':return 5;
    case '(':return 6;
    case ')':return 7;
    case '$':return 8;
    }
}


int shift()
{
stack[++top]=*(input+i++);
stack[top+1]='\0';
}


int reduce()
{
int i,len,found,t;
for(i=0;i<5;i++)//selecting handles
    {
    len=strlen(handles[i]);
    if(stack[top]==handles[i][0]&&top+1>=len)
        {
        found=1;
        for(t=0;t<len;t++)
            {
            if(stack[top-t]!=handles[i][t])
                {
                found=0;
                break;
                }
            }
        if(found==1)
            {
            stack[top-t+1]='E';
            top=top-t+1;
            strcpy(lasthandle,handles[i]);
            stack[top+1]='\0';
            return 1;//successful reduction
            }
        }
   }
return 0;
}



void dispstack()
{
int j;
for(j=0;j<=top;j++)
    printf("%c",stack[j]);
}



void dispinput()
{
int j;
for(j=i;j<l;j++)
    printf("%c",*(input+j));
}



void main()
{
int j;

input=(char*)malloc(50*sizeof(char));
printf("\nEnter the string\n");
scanf("%s",input);
input=strcat(input,"$");
l=strlen(input);
strcpy(stack,"$");
printf("\nSTACK\tINPUT\tACTION");
while(i<=l)
	{
	shift();
	printf("\n");
	dispstack();
	printf("\t");
	dispinput();
	printf("\tShift");
	if(prec[getindex(stack[top])][getindex(input[i])]=='>')
		{
		while(reduce())
			{
			printf("\n");
			dispstack();
			printf("\t");
			dispinput();
			printf("\tReduced: E->%s",lasthandle);
			}
		}
	}

if(strcmp(stack,"$E$")==0)
    printf("\nAccepted;");
else
    printf("\nNot Accepted;");
}

How to Use Mathematical Functions in Math.h in GCC Compiler for C

Linux operating systems use GCC (GNU Compiler Collection). In recent versions versions of GCC, it is not enough to include the line #include<math.h> to use functions in math.h header file. The most commonly used functions in math.h are sqrt, pow, abs, sin, cos, tan, exp, log, log10, ceil, floor etc. If you use any of the functions defined  in math.h header file, even if you include the #include<math.h> pre-processor directive, the compiler may show an error. In such case you should manually link to math.h file. Suppose you are going to compile a file myfile.c which uses functions under math.h header, you may use the following commands in terminal for gcc:

gcc myfile.c -lm

or

gcc myfile.c -o outputfilename -lm

-l option is used to manually link libraries. -lm directs the compiler to manually link libm. So, if we use the math library, we have to manually link it in gcc compilers. It is said to be for the reason that earlier processors were slow and floating point capabilities were limited. It is also said that it is for the reason embedded computing components are not having much computing capabilities especially for floating point operations or some of them even do not need it. So, math.h is avoided from automatic linking.