当前位置:网站首页>Experimental design - using stack to realize calculator
Experimental design - using stack to realize calculator
2022-07-05 12:21:00 【A finger leaf next to the giant】
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;
}
边栏推荐
- Principle of persistence mechanism of redis
- The evolution of mobile cross platform technology
- Automated test lifecycle
- How to clear floating?
- Halcon template matching actual code (I)
- Linux Installation and deployment lamp (apache+mysql+php)
- What is digital existence? Digital transformation starts with digital existence
- Image hyperspectral experiment: srcnn/fsrcnn
- MySQL storage engine
- Master-slave mode of redis cluster
猜你喜欢
HiEngine:可媲美本地的云原生内存数据库引擎
Redis master-slave mode
互联网公司实习岗位选择与简易版职业发展规划
Troubleshooting of high memory usage of redis in a production environment
16 channel water lamp experiment based on Proteus (assembly language)
Linux安装部署LAMP(Apache+MySQL+PHP)
Matlab imoverlay function (burn binary mask into two-dimensional image)
Wireless WiFi learning 8-channel transmitting remote control module
Reinforcement learning - learning notes 3 | strategic learning
Take you two minutes to quickly master the route and navigation of flutter
随机推荐
Halcon template matching actual code (I)
Swift - enables textview to be highly adaptive
Semantic segmentation experiment: UNET network /msrc2 dataset
MVVM framework part I lifecycle
强化学习-学习笔记3 | 策略学习
Intern position selection and simplified career development planning in Internet companies
MySQL basic operation -dql
[superhard core] is the core technology of redis
一类恒等式的应用(范德蒙德卷积与超几何函数)
POJ-2499 Binary Tree
Hiengine: comparable to the local cloud native memory database engine
ZABBIX customized monitoring disk IO performance
Redis highly available slice cluster
Handwriting blocking queue: condition + lock
手机 CPU 架构类型了解
Take you hand in hand to develop a service monitoring component
Correct opening method of redis distributed lock
Automated test lifecycle
MySQL regular expression
Check the debug port information in rancher and do idea remote JVM debug