Experimental design - using stack to realize calculator

1. Implement a simple calculator , Enter a field containing parentheses 、 Add, subtract, multiply and divide 、 Arithmetic expression string composed of remainder and other symbols , Output the value of the arithmetic expression . requirement ：
（1） The system can at least add 、 reduce 、 ride 、 except 、 Congruence operation ;
（2） Use the stack to realize and output the expression result .

1． Algorithm design and algorithm steps ：

Program analysis ： Calculator function realization , Use the sequence stack to realize the transformation from infix expression to suffix expression , Then proceed accordingly （+,-,*,/） Simple operation .
Infix expression to suffix expression ：
Apply for a continuous sequence stack character space for operator storage , In order to control the input and output sequence .
Save the suffix expression through a number array and a character array . Two arrays synchronize array subscripts , When an array of numbers is stored in a number , The character array is stored in a ！ Number as identification , And record the index of the array int Variable ++; When a character array is stored in a symbol , The subscript position of the number array defaults to 0, There is no need to mark , Just index the record array int Variable ++.
adopt flag Variable record character parsing status , If you continuously parse to numeric characters , Then number splicing , If you parse to characters , If flag Identify that the last read is a number , First, input the digital output into the array , Then analyze the characters .
If the character is ’(‘ Number , Or the top of the stack points -1, Then the characters are directly input into the stack ; If you encounter the right bracket , Perform stack out operation , And output the stack symbol （ Enter into the array ）, Until the left bracket is also out of the stack , Left parenthesis does not output ; When an operator is encountered , Pop up all stack top elements with priority greater than or equal to this operator , Then put the operator on the stack （ That is, if it is multiplication and division , Then multiply and divide out of the stack , New symbols on the stack ,
If it's addition and subtraction , Then, four operations will produce a stack , Stop the stack when encountering the left parenthesis , New symbols on the stack .） Final （ The character value is NULL） Put the elements in the stack out of the stack in turn , Output .
Suffix expression operation ：
Apply a continuous sequence of stack numbers （int） The space stores the read numbers , For expression operation .
If the subscript position of the number array is not NULL Then read the number , And put the numbers on the stack , If the position of the character array in the following table is not ！ No. indicates that the position of the suffix expression is an operator , Then stack two numbers for mathematical operation , Put the result on the stack after operation .
When reading the array, the subscript position is NULL It means that the suffix expression reads , Finished reading , Return the final result .

C Language implementation :

#define OK 1
#define ERROR 0
#define MAXSIZE 50
#include<stdio.h>
#include<stdlib.h> // Import and stock in documents  
#include<string.h>
typedef int status;  //status It's the type of function , Its value is the function result status code , Such as OK etc. 
                     // It is often used as a return value , Note that there Status It's an integer , If return OK  Represents the return value  1,return ERROR representative  0 

                     // Stack understanding : It's equivalent to a vertical linear table , For sequential storage , This concept is deeper ,
					 // Stack (Stack) It is a linear table that only inserts and deletes at the end of the table . Stack has the concept of empty stack , There will be a pointer that tracks the top of the stack top,
					 // Define when top by -1 Time is empty stack , top Less than StackSize, When the stack is full ,top=StackSize-1 
					 // extend : Summarize the concepts and differences between stack and heap  
					
/* Implement a simple calculator , Enter a field containing parentheses 、 Add, subtract, multiply and divide 、 Arithmetic expression string composed of remainder and other symbols , Output the value of the arithmetic expression . requirement ： （1） The system can at least add 、 reduce 、 ride 、 except 、 Congruence operation ; （2） Use the stack to realize and output the expression result .*/

// If you want the computer to have the standard to process us in general （ Infix ) The ability to express , There has to be ：
//1. Convert infix expression to suffix expression （ A symbol used by a stack to enter and exit operations ）
//2. The suffix expression is evaluated to get the result （ The number used by the stack to go in and out of operations ）


//c Language strings are composed of character arrays , You cannot use ordinary operators to operate on strings 
// The pointer can hold a string constant , Is read-only and not writable  
// Stack implementation uses the sequential storage of stack , String delimitation , And save the numbers in the array , Save symbols to a character array 

// To understand a little bit , data structure , Pay attention to the idea of Algorithm , Process learning ,c Language is a basic language ,
// Although there are many convenient encapsulation functions in the Library , But the basic realization is also achieved by writing code ,
// And maybe the function implementation is more complex than the program we write ourselves , More redundancy than our purpose ,
// Realize the function , Try to write the underlying code by yourself , And reduce the use of function calls  

// The character stack used when infix expression is converted to suffix expression  
typedef char ElemType; 

// Declare stack type  
typedef struct SqStack{
    
 ElemType data[MAXSIZE];
 int top; 
}SQTA ;
typedef struct SqStack *zhanChar;// The pointer , The variable that holds the address  
// The number stack used in the calculation of suffix expression  
typedef int ElemTypes; 
typedef struct SqStacks{
    
 ElemTypes data[MAXSIZE];
 int top; 
}SQTAs ;

typedef struct SqStacks *zhanInt;// The pointer , The variable that holds the address  
// If the defined structure is a pointer , When visiting members, use ->
// If you define a structure variable , When visiting members, use .
 
 int begin();// main interface , Perform different operations according to user input  
 int transform(char shizi[]); // Convert infix expression into suffix expression suitable for computer operation  
int count(char shiziChar[],	int shiziInt[]); // Operate on the suffix expression and return the result  


int transform(char shizi[]){
      // The array itself is an expression address  
	
	char shiziChar [100]={
    };// Used to store symbols after symbol sorting  // If the position is a number , Storage ! 
	int shiziInt [100]={
    }; // Used to store arrays of numbers , If the position is a character , Is stored as 0 
	char *p=shizi; //shizi Itself is also a pointer , But because of the name , Here we still use pointer p Instead of  
	int a =0;// Used to record the number after separation 
	int index=0;// Used to record 
	int flag=1;// Used to record whether you are spelling numbers   namely ( Whether it is in the state of spelling numbers ) 
	zhanChar zc=(zhanChar)malloc(sizeof(SQTA ));// If the allocation is successful, a pointer to the allocated memory is returned 
	zc->top=-1;
	
do{
    
	  
	if(*p>=48&& *p<=57){
      // Read a numeric character  
       a *=10;
		a+=*p-48;
		flag=1; 
	}else{
                   // Read a character , Or the end of the string  
		if(flag==1){
    
			shiziInt[index]=a;  // Input the spliced numbers into the array  
			shiziChar[index]='!';// Use this position ! identification 
			index++; 
			a=0;         
						     // Here we are , It is equivalent to entering a number  
		}
		if(*p==NULL){
        
			//printf(" Finished reading ");
			while(zc->top!=-1){
    
				shiziChar[index]=zc->data[zc->top];
				index++;
				zc->top--;
			}
			
				break;
		} else if(zc->top==-1||*p=='('){
       //  If the character is （ perhaps zc->top==-1, Direct stack  
			zc->top++;                  
			zc->data[zc->top]=*p;
		}else if(*p==')'){
    
			// Right parenthesis encountered , Perform stack out operation , And output the stack symbol , Until the left bracket is also out of the stack , Left parenthesis does not output 
			// encounter +--/  when , Pop up all stack top elements with priority greater than or equal to this operator , Then put the operator on the stack 
			// Finally, the elements in the stack will be out of the stack one by one , Output  
			do{
    
				if(zc->data[zc->top]=='('){
    
					zc->top--;  // 
					break;
				}else{
    
					
			shiziChar[index]=zc->data[zc->top];
				index++;
			zc->top--;
				} 
			}while(1);
			
		} else if(*p=='*'||*p=='/'){
      // If it's multiplication and division , Then multiply and divide out of the stack , New symbols on the stack  
			while(zc->top>=0&&zc->data[zc->top]=='*'||zc->data[zc->top]=='/'){
    
				shiziChar[index]=zc->data[zc->top];
				index++;
				zc->top--;
			}
			zc->top++;
			zc->data[zc->top]=*p;
			
		}else if(*p=='+'||*p=='-'){
      // If it's addition and subtraction , Then, four operations will produce a stack , Stop the stack when encountering the left parenthesis , New symbols on the stack  
			while(zc->top>=0&&zc->data[zc->top]!='('){
    
				shiziChar[index]=zc->data[zc->top];
				index++;
				zc->top--;
			}
			
			zc->top++;  
			zc->data[zc->top]=*p;
			
		}
		     
		flag=0;
		
		
	}
	 p++;
	 // If you just enter a pure number  
	 
	}while(1);
	int i=0;
	printf("\n");
	while(shiziInt[i]!=NULL||shiziChar[i]!=NULL){
      // The number array defaults to 0 
		if(shiziInt[i]!=NULL){
    
			printf("%d",shiziInt[i]);
			
		}else if(shiziChar[i]!='!'){
    
			printf("%c",shiziChar[i]);
		}
			i++;
		}
			printf("\n");

      int counts=0;
      counts=count(shiziChar,shiziInt);
	return counts;
}
// printf("%\n",p); 
// printf("%s\n",shizi); 
// printf("%c\n",shizi[0]);
// printf("%p\n",shizi);
// printf("%p\n",shizi[0]);
// printf("%p\n",shizi[1]);

 int count(char shiziChar[],int shiziInt[]){
    
	int i=0;// Used to record 
	zhanInt zi=(zhanInt)malloc(sizeof(SQTAs ));// If the allocation is successful, a pointer to the allocated memory is returned 
	zi->top=-1;
	int count=0; // The calculated value , Or the end result 
	int count1=0,count2=0; 
	while(shiziInt[i]!=NULL||shiziChar[i]!=NULL){
    
		if(shiziInt[i]!=NULL){
       // Enter the stack when reading the number  
			zi->top++;
			zi->data[zi->top]=shiziInt[i];
			
		}else if(shiziChar[i]!='!'){
      // Operate when encountering characters  
			      count2=zi->data[zi->top];   // Record the top of the stack  
				      zi->top--;
					   count1=zi->data[zi->top];  // Record the top of the stack -1 
			 if(shiziChar[i]=='+'){
    
			 	count=count1+count2;
			 }else if(shiziChar[i]=='-'){
    
			 	count=count1-count2;
			 }else if(shiziChar[i]=='*'){
    
			 	count=count1 * count2;
			 }else if(shiziChar[i]=='/'){
     
			 	count=count1 / count2;
			 }
			 zi->data[zi->top]=count;
		} 
		   
			i++;
		}
		count=zi->data[zi->top];
		    zi->top--;
		
		return count;
} 


int begin(){
    
	printf("------ McDull gives you a calculator --------\n");
  	char shizi[100]=""; // The final formula  
	printf(" Give me the formula to calculate ：\n"); 
	scanf("%99s",&shizi);
  	printf(" McDull is trying to calculate ....");
  	printf("%d",transform(shizi));
  	} 
int main() {
    
	 
    begin();
    return 1;
}