Because in the school is really too idle, so wrote an expression evaluation of the C language program, hope big guys can correct.
Basic idea:
Just like putting an elephant in a refrigerator, we need to evaluate the expression in three steps.
- Enter an infix expression (the expression we usually see)
- Convert infix expression to suffix expression
- Evaluate according to suffix expression.
Step 1:
It's easy to enter an infix expression. You can do it with a brain. However, in order to make the code easier, here are some specifications for the input expression.
- All input characters and numbers are separated by spaces
- The multiplication sign cannot be omitted
- The number should be followed by a space before entering the operator.
Step 2:
The basic process from infix expression to suffix expression is to read each object of infix expression from beginning to end, and treat different pairs of objects according to different situations, which can be divided into the following six cases:
- If it is a space, it is considered as a delimiter and will not be processed
- If it is an operand, it is output directly
- If it is an open bracket, push it into the stack
- If it is a right bracket, it indicates that the infix expression in the bracket has been scanned. Pop up the operator at the top of the stack and output it until it meets the left bracket (the left bracket is not output)
- If an operator is encountered, if the stack is empty now, put the operator directly into the stack. If it is not empty, compare the priority of this operator with the operator at the top of the stack. If the priority of this operator is less than or equal to the operator at the top of the stack, output the operator at the top of the stack, and compare this operator with the new operator at the top of the stack again, Until the priority of the operator is higher than that of the operator at the top of the stack, and then press the operator on the stack
- If all elements in infix expression are processed, operators remaining in stack will be output together.
After executing all the processes, we output an infix expression.
Of course, in the actual implementation, we still have requirements for the format. Suffix expression is different from infix expression. Many numbers may be connected together in suffix expression. Therefore, for continuous output numbers, we need to add spaces in the middle to divide them, so as to distinguish whether it is a two digit decimal number or two one digit decimal numbers.
Step 3:
According to the evaluation of suffix expression, I think if you learn the knowledge of stack and understand what suffix expression is, you can easily understand how to use stack to evaluate suffix expression. Please see another blog for details Click here to see the implementation of stack and the evaluation of suffix expression.
The three steps are understood. How to combine these three steps?
Before introducing, make complaints about C language, and even a stack that can be directly adjusted. If I want to call two different stacks, one int and one char, I need to write two sets of definitions, otherwise I can't achieve them in a single program. (it may be possible, but I won't, I'm sorry)
union
First, we encapsulate the contents of step 2 and step 3, customize two header files, and implement the contents. In the process of definition, I found that some definitions are repeated, so we put the repeatedly defined things into another header file.
| file name | effect |
|---|---|
| same.h | Some duplicate macro definitions |
| TransformationToInfixExpression.h | Defines the header file that is converted to a suffix expression |
| ExpressionEvaluation.h | Header file that defines the evaluation of suffix expressions |
| TransformationToInfixExpression.c | Implement the header file with the same name as before |
| ExpressionEvaluation.c | Implement the header file with the same name as before |
| test.c | The main function is used to realize the first step |
same.h
#define MAXOP 100 /* Maximum possible length of operand sequence*/
#define INFINITY 1e9 /* Represents positive infinity*/
#define ERROR -INFINITY
typedef int Position;
typedef char ElementType1;
typedef double ElementType2;
struct SNode1{
ElementType1 *Data; /*An array of storage elements*/
Position Top; /*Stack top pointer*/
int MaxSize; /*Maximum stack capacity*/
};
struct SNode2{
ElementType2 *Data; /*An array of storage elements*/
Position Top; /*Stack top pointer*/
int MaxSize; /*Maximum stack capacity*/
};
TransformationToInfixExpression.h
//TransformationToInfixExpression.h #ifndef _TRANSFORMATIONTOINFIXEXPRESSION_H_ #define _TRANSFORMATIONTOINFIXEXPRESSION_H_ //Structure and function declarations typedef struct SNode1 *PtrToSNode1; typedef PtrToSNode1 Stack1; typedef char ElementType1; //1. Convert a infix expression to a suffix expression void TransformationToInfixExpression(char* Expr, char* Aim); //Determine the priority of characters int Priority(char a,char b); Stack1 CreateStack1(int MaxSize); int IsFull1(Stack1 S); int Push1(Stack1 S,ElementType1 X); int IsEmpty1(Stack1 S); ElementType1 Pop1(Stack1 S); ElementType1 Peek1(Stack1 S); #endif
ExpressionEvaluation.h
//ExpressionEvaluation.h
//Conditional compilation
#ifndef _EXPRESSIONEVALUATION_H_
#define _EXPRESSIONEVALUATION_H_
//Structure and function declarations
typedef enum {true,false} bool;
typedef enum {num, opr, end} Type;
typedef struct SNode2 *PtrToSNode2;
typedef PtrToSNode2 Stack2;
typedef double ElementType2;
Stack2 CreateStack2(int MaxSize);
bool IsFull2(Stack2 S);
bool Push2(Stack2 S,ElementType2 X);
bool IsEmpty2(Stack2 S);
ElementType2 Pop2(Stack2 S);
ElementType2 Peek2(Stack2 S);
Type GetOp(char * Expr, int * start,char * str);
ElementType2 PostfixExp(char* Expr);
#endif
TransformationToInfixExpression.c
#include"TransformationToInfixExpression.h"
#include"same.h"
#include"ExpressionEvaluation.h"
#include<string.h>
#include<ctype.h>
#include<stdio.h>
#include<stdlib.h>
Stack1 CreateStack1(int MaxSize){
Stack1 S = (Stack1)malloc(sizeof(Stack1));
S->Data = (ElementType1*)malloc(MaxSize*sizeof(ElementType1));
S->Top = -1;
S->MaxSize = MaxSize;
return S;
}
int IsFull1(Stack1 S){
return (S->Top == S->MaxSize - 1);
}
int Push1(Stack1 S,ElementType1 X){
if(IsFull1(S)){
printf("Stack full\n");
return 0;
}else{
S->Data[++(S->Top)] = X;
return 1;
}
}
int IsEmpty1(Stack1 S){
return (S->Top == -1);
}
ElementType1 Pop1(Stack1 S){
if(IsEmpty1(S)){
printf("Stack empty 1\n");
return (ElementType1)ERROR;
}else{
return S->Data[(S->Top)--];
}
}
ElementType1 Peek1(Stack1 S){
if(IsEmpty1(S)){
printf("Stack empty 2\n");
return (ElementType1)ERROR;
}else{
return S->Data[(S->Top)];
}
}
void TransformationToInfixExpression(char* Expr, char* Aim){
int n = strlen(Expr);
Stack1 S = CreateStack1(MAXOP);
int j = 0;
for (int i = 0; i < n; i++){
if (Expr[i] == ' '){
if(j != 0 && Aim[j-1] != ' '){
Aim[j++] = Expr[i];
}
continue;
} else if(isdigit(Expr[i]) || Expr[i] == '.'){
Aim[j++] = Expr[i];
} else if(Expr[i] == '('){
Push1(S,Expr[i]);
} else if(Expr[i] == ')'){
char c = Pop1(S);
while(c != '('){
Aim[j++] = c;
Aim[j++] = ' ';
c = Pop1(S);
}
} else {
if(!IsEmpty1(S)){
char c = Peek1(S);
while(Priority(Expr[i],c) <= 1){
Aim[j++] = Pop1(S);
Aim[j++] = ' ';
if(!IsEmpty1(S)){
c = Peek1(S);
}else{
break;
}
}
}
Push1(S,Expr[i]);
}
}
Aim[j++] = ' ';
while(!IsEmpty1(S)){
Aim[j++] = Pop1(S);
Aim[j++] = ' ';
}
}
int Priority(char a,char b){
/*
a==b 0;
a<b 1;
a>b 2;
*/
if(a == '*' || a == '/'){
if(b == '*' || b == '/'){
return 0;
}else{
return 2;
}
}else if(a == '+' || a == '-'){
if(b == '*' || b == '/'){
return 1;
}else if(b == '+' || b == '-'){
return 0;
}else {
return 2;
}
}
}
ExpressionEvaluation.c
//This program uses the stack to find the value of suffix expression
#include"ExpressionEvaluation.h"
#include"same.h"
#include"TransformationToInfixExpression.h"
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
Stack2 CreateStack2(int MaxSize){
Stack2 S = (Stack2)malloc(sizeof(Stack2));
S->Data = (ElementType2*)malloc(MaxSize*sizeof(ElementType2));
S->Top = -1;
S->MaxSize = MaxSize;
return S;
}
bool IsFull2(Stack2 S){
return (S->Top == S->MaxSize - 1);
}
bool Push2(Stack2 S,ElementType2 X){
if(IsFull2(S)){
printf("Stack full\n");
return false;
}else{
S->Data[++(S->Top)] = X;
return true;
}
}
bool IsEmpty2(Stack2 S){
return (S->Top == -1);
}
ElementType2 Pop2(Stack2 S){
if(IsEmpty2(S)){
printf("Stack empty\n");
return (ElementType2)ERROR;
}else{
return S->Data[(S->Top)--];
}
}
ElementType2 Peek2(Stack2 S){
if(IsEmpty2(S)){
printf("Stack empty 2\n");
return (ElementType2)ERROR;
}else{
return S->Data[(S->Top)];
}
}
Type GetOp(char * Expr, int * start,char * str){
/*Read the next object (operand or operator) from * start and save it in the string str*/
int i = 0;
/*Skip spaces before expressions*/
while((str[0] = Expr[(*start)++])==' ');
while(str[i]!=' ' && str[i] != '\0')
str[++i] = Expr[(*start)++];
if(str[i] == '\0') /*If you read the end of the input*/
(*start)--; /*start Point to Terminator*/
str[i] = '\0'; /*End the acquisition of an object*/
if(i == 0) return end; /*It's over*/
/*If str[0] is a number, or a symbol followed by a number*/
else if(isdigit(str[0]) || isdigit(str[1]))
return num; /*Indicates that there is only a number stored in str*/
else
return opr; /*Indicates that an expression is stored in str*/
}
ElementType2 PostfixExp(char* Expr){
Stack2 S;
Type T;
ElementType2 Op1,Op2;
char str[MAXOP];
int start = 0;
/*Request a new stack*/
S = CreateStack2(MAXOP);
Op1 = Op2 = 0;
while((T = GetOp(Expr,&start,str))!=end){
/*When the end is not read*/
if(T == num){
Push2(S,atof(str));
} else {
if(!IsEmpty2(S)) Op2 = Pop2(S);
else Op2 = INFINITY;
if(!IsEmpty2(S)) Op1 = Pop2(S);
else Op2 = INFINITY;
switch(str[0]){
case'+':Push2(S,Op1 + Op2);break;
case'*':Push2(S,Op1 * Op2);break;
case'-':Push2(S,Op1 - Op2);break;
case'/':
if(Op2 != 0.0)/*Check whether the denominator of division is equal to 0*/
Push2(S,Op1 / Op2);
else{
printf("Error: Division denominator is 0\n");
Op2 = INFINITY;
}
break;
default:
printf("Error: unknown operator:%s\n",str);
Op2 = INFINITY;
break;
}
if(Op2 == INFINITY) break;
}
}
if(Op2 <INFINITY)/*Finished processing expression*/
if(!IsEmpty2(S))/*At this time, the stack is normal*/
Op2 = Pop2(S);
else Op2 = INFINITY; /*Otherwise, the mark is wrong*/
free(S); /*Release stack*/
return Op2;
}
test.c
#include"ExpressionEvaluation.h"
#include"TransformationToInfixExpression.h"
#include"same.h"
#include<stdio.h>
int main(){
printf("Please enter infix expression:\n");
char Expr[MAXOP] = {0};
char Aim[MAXOP] = {0};
gets(Expr);
TransformationToInfixExpression(Expr,Aim);
printf("The converted suffix expression is:%s\n",Aim);
double r = PostfixExp(Aim);
printf("The calculation results are:%.4lf\n",r);
}
Then it's done. Conduct joint debugging on these C files to run the final program. Let's see the effect ^ -^
effect:
The compilation command is the first line: the error is reported here because gets is unsafe. It is recommended to use fgets here. It doesn't matter here, which will not affect our normal use.
Execute test file:
Here we can enter an expression that we can understand, and then directly output the result.
If I think my writing is good, I hope I can praise it. If there is a better plan, you are also welcome to give me more advice.
- For ideas and some codes, refer to data structure (Second Edition) - Higher Education Press