Stack and queue practice (C language): Demon King's language

  A lot of things are changing , I'm the only one who won't C++ It's just C Stupid fool

The demon king's language

  My thoughts ： Local stack , Overall queue .

1 queue ： The whole string processing adopts queue . fifo , Deal with one by one .

2 Stack ： encounter “()" Create a stack , First in, then out , Realization “ Come back ”. Continue queue processing after processing .

 

First pass

#include <stdio.h>
#include <stdlib.h>
// Demon language  
typedef struct QNode {
   char a;
    struct QNode* next;
}QNode;
// The team  
QNode* enQueue(QNode* rear, char x) {
    QNode* enElem = (QNode*)malloc(sizeof(QNode));
    enElem->a = x;
    enElem->next = NULL;//1、 Wrap queued elements with nodes 
    rear->next = enElem;//2、 New nodes and rear Nodes establish logical relationships 
    rear = enElem;//3、rear Point to a new node   
    return rear;// Return to new rear, Prepare for new elements to join the team 
}
// Out of the team 
char DeQueue(QNode* top) {
    if (top->next == NULL)
        return '0';
    QNode* p = top->next;
    top->next = p->next;
    char a = p->a;
    free(p);
    return a;
}
// Push 
QNode* push(QNode* stack, char x)
{
    QNode* line = (QNode*)malloc(sizeof(QNode));
    line->a=x;
    line->next = stack;// New node  
    stack = line;// to update  
    return stack;
}
// Out of the stack 
char pop(QNode* stack)
{
    char a; 
    if (stack->next != NULL&&stack) {
        QNode* p = stack;
        stack = stack->next;
        a = p->a;
        free(p);
        return a;
    }
    else
        return '0'; 
}
int main()
{
    char a,b; 
    QNode* queue = (QNode*)malloc(sizeof(QNode));
    queue->next = NULL;
    QNode* q = queue,*top=queue;
    while (1)
    {
         a=getchar();
        if( a>='a'&&a<='z' || a == 'A' || a =='B'||a=='('||a==')')
            q = enQueue(q, a);
        else break;
    }  
    while (top)
    { // Enter the queue normally 
        a = DeQueue(top);
        if (a >= 'a' && a <= 'z')
            printf("%c",a);// Human language 
        else if (a == 'B')
            printf("tsaedsae");
        else if (a == 'A')
            printf("sae");
        else //stack a-->'('
        {
            b= DeQueue(top);// to update 
            QNode*stack= (QNode*)malloc(sizeof(QNode));
            while (a != ')')
            {
                a= DeQueue(top);
                stack = push(stack, a);
            }
            pop(stack); //pop(stack);// eject ”）
            while (1)
            {
                if (b >= 'a' && b <= 'z')
                    printf("%c", b);// Human language 
                else if (b == 'B')
                    printf("tsaedsae");
                else //if (b == 'A')
                    printf("sae");

                a = pop(stack);
                if (a >= 'a' && a <= 'z')
                    printf("%c", a);// Human language 
                else if (a == 'B')
                    printf("tsaedsae");
                else if (a == 'A')
                    printf("sae");
                else //if (a == '0')
                    break;
            }
        }
    }
    getchar(); 
    return 1;
}

The result error , Use several printf Check it out , I think it's because pop Function return value is not stack, Did not return the changed results , As a result, the stored in the stack has never been deleted successfully .

Second times

#include <stdio.h>
#include <stdlib.h>
// Demon language  
typedef struct QNode {
   char a;
    struct QNode* next;
}QNode;
// The team  
QNode* enQueue(QNode* rear, char x) {
    QNode* enElem = (QNode*)malloc(sizeof(QNode));
    enElem->a = x;
    enElem->next = NULL;//1、 Wrap queued elements with nodes 
    rear->next = enElem;//2、 New nodes and rear Nodes establish logical relationships 
    rear = enElem;//3、rear Point to a new node   
    return rear;// Return to new rear, Prepare for new elements to join the team 
}
// Out of the team 
char DeQueue(QNode* top) {
    if (top->next == NULL)
        return '0';
    QNode* p = top->next;
    top->next = p->next;
    char a = p->a;
    free(p);
    return a;
}
// Push 
QNode* push(QNode* stack, char x)
{
    QNode* line = (QNode*)malloc(sizeof(QNode));
    line->a=x;
    line->next = stack;// New node  
    stack = line;// to update  
    return stack;
}
// Out of the stack 
QNode* pop(QNode* stack)
{
    if (stack->next != NULL&&stack) {
        QNode* p = stack;
        stack = stack->next;
        free(p);
    }
     return stack; 
}
int main()
{
    char a,b; 
    QNode* queue = (QNode*)malloc(sizeof(QNode));
    queue->next = NULL;
    QNode* q = queue,*top=queue;
    while (1)
    {
         a=getchar();
        if( a>='a'&&a<='z' || a == 'A' || a =='B'||a=='('||a==')')
            q = enQueue(q, a);
        else break;
    }  
    while (top)
    { // Enter the queue normally 
        a = DeQueue(top);
        if (a >= 'a' && a <= 'z')
            printf("%c",a);// Human language 
        else if (a == 'B')
            printf("tsaedsae");
        else if (a == 'A')
            printf("sae");
        else //stack a-->'('
        {
            b= DeQueue(top);// to update 
            QNode*stack= (QNode*)malloc(sizeof(QNode));
            while (a != ')')
            {
                a= DeQueue(top);
                stack = push(stack, a);
            }
            //stack=pop(stack); // eject ”）
            while (1)
            {
                if (b >= 'a' && b <= 'z')
                    printf("%c", b);// Human language 
                else if (b == 'B')
                    printf("tsaedsae");
                else //if (b == 'A')
                    printf("sae");

                if (stack->next != NULL)
                    a = stack->next->a;
                else
                    break;
                stack = pop(stack);
                if (a >= 'a' && a <= 'z')
                    printf("%c", a);// Human language 
                else if (a == 'B')
                    printf("tsaedsae");
                else if (a == 'A')
                    printf("sae");
                else //if (a == '0')
                    break;
            }
        }  // Actually stack and queue The definition is the same , But the operation is different .
    }
    return 1;
}

There is no problem with the local test, but the result is determined as timeout （ Time consuming 1006ms）.

problem ： Low efficiency , should First （ Store it upside down ） Stored in the stack , Local use queue .

Third times ： Array

Arrays are omnipotent , Blowing array . 

#include <stdio.h>
void stack(int i, int k, char word[])
{// Ideas ： Recursively solve the multi-level nesting problem 
// function ： Print the contents of a pair of parentheses 
// Pass in the parameter ：i,k; The first and ')' The location of ,word; character string 
	//i： Used to print the first digit 
	int j, begin;
	if (i == k )return;// Empty parenthesis 
	else
	{// first place 
		 if (word[i] == 'B')
			printf("tsaedsae");
		else if (word[i] == 'A')
			printf("sae");
		else printf("%c", word[i]);// Because I didn't consider （（）） situation 
	}

	for (j = k - 1;j > i; j--)
	{
		if (word[j] == '(')		continue;
		if (word[j] == ')')
		{
			for (begin = j; word[begin] != '('; begin--)	;
			stack(begin+1, j, word);
			j = begin;
		}
		else
		{
			 if (word[j] == 'B')
				printf("tsaedsae");
			else if (word[j] == 'A')
				printf("sae");
			else printf("%c", word[j]);

		}
		if (word[i] == 'B')
			printf("tsaedsae");
		else if (word[i] == 'A')
			printf("sae");
		else printf("%c", word[i]);// Because I didn't consider （（）） situation 
	}
}
int main()
{
	char word[1000] = { 0 };	scanf_s("%s", word,1000);
	int i=0, begin=0,k;
	while (1)
	{
		 if (word[i] == 'B')
			printf("tsaedsae");
		else if (word[i] == 'A')
			printf("sae");
		else if (word[i] == ')')
			;
		else if (word[i] == '(')
		{
			begin = i + 1; i++;
			for (k = 1; k ; i++)
			{// find end
				if (word[i] == '(')
					k++;//k Mark the number of parentheses 
				else if (word[i] == ')')
					k--;
				if (k <= 0)// once k=0, break instant
					break;
			}
			stack(begin,i, word);
		}
		else//(word[i] >= 'a' && word[i] <= 'z')
			 printf("%c", word[i]);
		i++;
		if(word[i]==0)			break;// End 
	}	
	return 0;
}

The title clearly does not say that there is CDEF situation , How can I think of other capital letters to consider , Just change this point

 

Add ：

When it comes to continuous nesting , Different understandings lead to different results .
such as ：                (RMRGRJRDRORsaeRGRDFGA)=RsaeRGRFRDRRRGRRReRaRsRRRORRRDRRRJRRRGRRRMR
   still ((RGAODJGM)DFGA) =RsaeRGRFRDRRRGRRRsaeRRRORRRDRRRJRRRGRRRMR

bye ！ Devil ！