表达式求值(后缀表达式)

后缀表达式

后缀表达式是给计算机去看的,一个个压进栈中; 遇到操作符就计算再将计算出的结果压到栈中;最后弹出结果。

1.栈的初始化(动态存储)

typedef struct {ElemType* data;int top;
}Stack;
//初始化
Stack* initStack()
{Stack* s = (Stack*)malloc(sizeof(Stack));s->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);s->top = -1;return s;
}

2.用了一个枚举类型去存储一些操作

typedef enum
{   //左右括号  LEFT_PARE, RIGTH_PARE,ADD,SUB,MUL,DIV,MOD,EOS,NUM 
}contentType;

3.对栈的入栈和出栈操作

// 入栈操作
int push(Stack* s, ElemType elem) {if (s->top == MAXSIZE - 1) {printf("栈满，无法入栈\n");return 0;}s->top++;s->data[s->top] = elem;return 1;
}
int pop(Stack* s, ElemType* elem) {if (s->top == -1) {printf("栈空，无法出栈\n");return 0;}*elem = s->data[s->top];s->top--;return 1;
}

4.对操作数的具体操作

我们来模拟当index = 0时在字符数组中下标为0的字符是8 然后可以得到 symbol = '8'

进入switch中可以返回NUM

在eval函数中,token为NUM就识别为数字,就压栈

不断的循环最后完成表达式求值

contentType getToken(char* symbol, int* index)
{*symbol = expr[*index]; //先将0的地址传过来现在值为8*index = *index + 1; //index变2switch (*symbol)//将8存进去{case'(':return LEFT_PARE;case')':return RIGTH_PARE;case'+':return ADD;case'-':return SUB;case'*':return MUL;case'/':return DIV;case'%':return MOD;case'\0':return EOS;default:return NUM;  //数字8 返回NUM}
}

int eval(Stack* s)
{char symbol;int op1, op2;int index = 0;contentType token; //字符的类型token = getToken(&symbol, &index);//识别到是哪个字符,返回什么算法ElemType result;while (token != EOS) {//一直循环到字符数组的\0结束if (token == NUM)//如果是数字就压栈{push(s, symbol - '0');// 字符减去'0' 是数值}else{pop(s, &op2); //如果是操作符就弹出进行计算pop(s, &op1);
switch (token){case ADD:push(s, op1 + op2);break;case SUB:push(s, op1 - op2);break;case MUL:push(s, op1 * op2);break;case DIV:push(s, op1 / op2);break;case MOD:push(s, op1 % op2);break;default:break;}}token = getToken(&symbol, &index);
}pop(s, &result);printf("%d\n", result);return 1;
}

5.一个全局变量,字符数组

char expr[] = "82/2+56*-";

完整代码如下

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef int ElemType;typedef struct {ElemType* data;int top;
}Stack;typedef enum
{	//左右括号	LEFT_PARE, RIGTH_PARE,ADD,SUB,MUL,DIV,MOD,EOS,NUM 
}contentType;char expr[] = "82/2+56*-";//初始化
Stack* initStack()
{Stack* s = (Stack*)malloc(sizeof(Stack));s->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);s->top = -1;return s;
}// 入栈操作
int push(Stack* s, ElemType elem) {if (s->top == MAXSIZE - 1) {printf("栈满，无法入栈\n");return 0;}s->top++;s->data[s->top] = elem;return 1;
}
int pop(Stack* s, ElemType* elem) {if (s->top == -1) {printf("栈空，无法出栈\n");return 0;}*elem = s->data[s->top];s->top--;return 1;
}
contentType getToken(char* symbol, int* index)
{*symbol = expr[*index]; //先将0的地址传过来现在值为8*index = *index + 1; //index变2switch (*symbol)//将8存进去{case'(':return LEFT_PARE;case')':return RIGTH_PARE;case'+':return ADD;case'-':return SUB;case'*':return MUL;case'/':return DIV;case'%':return MOD;case'\0':return EOS;default:return NUM;  //数字8 返回NUM}
}int eval(Stack* s)
{char symbol;int op1, op2;int index = 0;contentType token; //字符的类型token = getToken(&symbol, &index);//识别到是哪个字符,返回什么算法ElemType result;while (token != EOS) {//一直循环到字符数组的\0结束if (token == NUM)//如果是数字就压栈{push(s, symbol - '0');// 字符减去'0' 是数值}else{pop(s, &op2); //如果是操作符就弹出进行计算pop(s, &op1);switch (token){case ADD:push(s, op1 + op2);break;case SUB:push(s, op1 - op2);break;case MUL:push(s, op1 * op2);break;case DIV:push(s, op1 / op2);break;case MOD:push(s, op1 % op2);break;default:break;}}token = getToken(&symbol, &index);}pop(s, &result);printf("%d\n", result);return 1;
}
int main()
{Stack* s = initStack();eval(s);
}