数据结构——表达式求值源程序（一）

向右看齐 2022-08-03 00:23 138阅读 0赞

效果如下：

![SouthEast][]

/\*表达式求值\*/

\#include <stdio.h>

\#define OK 1  
\#define ERROR -1  
\#define SIZE 100  
\#define ADDSIZE 20  
\#include<stdlib.h>  
typedef struct\{  
int stacksize/\*data\[MAXSIZE\]\*/;  
int \*top;  
int \*base;  
\}seqstack; /\* 顺序栈的定义\*/  
int In(char c);  
void InitStack(seqstack &s);  
int Empty(seqstack \*s);  
void Push(seqstack &s, int e);  
int Pop(seqstack &s);  
int GetTop(seqstack s);  
int Operate(int a,char r,int b);  
char Proceed(char op,char c);  
int EvalExpres(void);  
  
  
/\* 定义两个栈分别存放运算符和操作数\*/  
seqstack StackR,StackD;  
/\*主函数\*/  
int main()  
\{  
int v;  
  
printf("...............算术表达式的求值.....................\\n\\n");  
v = EvalExpres();  
printf("The result is:%d\\n",v);  
return 0;  
\}  
void InitStack(seqstack &s) //构造运算符栈  
\{  
s.base = (int \*)malloc(SIZE \* sizeof(int));  
s.top = s.base;  
s.stacksize = SIZE;  
\}  
  
int Empty(seqstack s) /\* 判断栈是否为空\*/  
\{  
if(s.top == s.base)  
return 1;  
else  
return 0;  
\}  
  
  
void Push(seqstack &s, int e)  
\{  
if(s.top - s.base >= s.stacksize)  
\{  
s.base = (int \*) realloc(s.base, (s.stacksize + ADDSIZE) \* sizeof(int));  
s.top = s.base + s.stacksize;  
s.stacksize += ADDSIZE;  
\}  
\*s.top++ = e;  
\}  
int Pop(seqstack &s)  
\{  
int e;  
if(s.top == s.base)  
return ERROR;  
e = \* --s.top;  
return e;  
\}  
int GetTop(seqstack s)  
\{  
int e;  
if(s.top==s.base)  
return ERROR;  
else  
\{  
e=\*(s.top-1);  
\}  
return e;  
\}  
  
  
int In(char c) /\*问题2：解决In函数问题:判断C是否为运算符是返回1否则返回0\*/  
\{  
char ch\[7\]=\{'+','-','\*','/','\#','(',')'\};  
int i;  
for(i = 0; i < 7; i++)  
if(c == ch\[i\])  
return 1;  
return 0;  
\}  
char Proceed(char op,char c) /\*op为栈顶元素，c为当前读入的运算符,比较二者的优先级\*/  
\{ /\*问题1：解决Proceed函数\*/  
char ch;  
if(op=='(' && c==')' || op=='\#' && c=='\#' )  
ch = '=';  
else  
if(op=='+' || op=='-') /\*栈顶元素为'+'或'-'的时候\*/  
switch(c)  
\{  
case '+':  
case '-':  
case ')':  
case '\#': ch = '>'; break;  
case '\*':  
case '/':  
case '(': ch = '<';  
\}  
else  
if(op=='\*' || op=='/') /\*栈顶元素为'\*'或'/'的时候\*/  
switch(c)  
\{  
case '+':  
case '-':  
case '\*':  
case '/':  
case ')':  
case '\#': ch = '>'; break;  
case '(': ch = '<';  
\}  
else  
if(op=='(') /\*栈顶元素为'('的时候\*/  
switch(c)  
\{  
case '+':  
case '-':  
case '\*':  
case '/':  
case '(': ch = '<'; break;  
case '\#': printf("Error!\\n"); exit(0);  
\}  
else  
if(op==')') /\*栈顶元素为')'\*/  
switch(c)  
\{  
case '+':  
case '-':  
case '\*':  
case '/':  
case '\#': ch = '>'; break;  
case '(': printf("Error!\\n"); exit(0);  
\}  
else  
if(op=='\#') /\*栈顶元素为'\#'的时候\*/  
switch(c)  
\{  
case '+':  
case '-':  
case '\*':  
case '/':  
case '(': ch = '<'; break;  
case ')': printf("Error!\\n"); exit(0);  
\}  
return ch;  
\}  
/\* 问题3：解决Operate函数\*/  
int Operate(int a,char r,int b) /\*返回由aRb的值 \*/  
\{  
int s;  
int d1 = a;  
int d2 = b; /\*把字符ab变为对应数字\*/  
switch(r)  
\{  
case '+': s = d1+d2; break;  
case '-': s = d2-d1; break;  
case '\*': s = d1\*d2; break;  
case '/': s = d2/d1;  
\}  
return (s+'0'); \}  
int EvalExpres(void) /\* 表达式求解函数\*/  
\{  
int a,b,i=0,s=0;  
char c\[80\],r;  
InitStack(StackR); /\* 初始化存放运算符的栈\*/  
Push(StackR,'\#'); /\* 进栈 \*/  
InitStack(StackD); /\* 初始化存放操作数的栈\*/  
printf(" 请输入表达式并以'\#'结束：\\n");  
gets(c);  
while(c\[i\]!='\#' || GetTop(StackR)!='\#')  
\{  
if(!In(c\[i\])) /\* 判断读入的字符不是运算符 是则进栈\*/  
\{  
if(c\[i\] >= '0' && c\[i\] <= '9')  
\{  
s += c\[i\]-'0';  
while(!In(c\[++i\])) /\*此处实现的功能为当输入的数字为多位数时\*/  
\{  
s\*=10;  
s += c\[i\]-'0';  
\}  
Push(StackD,s+'0');  
s = 0;  
\}  
else  
\{  
printf("你输入的表达式有误!\\n");  
return 0;  
\}  
\}  
else  
switch(Proceed(GetTop(StackR),c\[i\])) /\* 此函数用来比较读取的运算符和栈顶运算符的优先级\*/  
\{  
case '<': /\* 栈顶的元素优先级高\*/  
Push(StackR,c\[i\]);  
i++;  
break;  
case '=': /\* 遇到匹配的小括号时则去掉他\*/  
Pop(StackR);  
i++;  
break;  
case '>': /\* 栈顶的优先级低则出栈并将结果写入栈内\*/  
r = Pop(StackR);  
a = Pop(StackD)-'0';  
b = Pop(StackD)-'0';  
Push(StackD,Operate(a,r,b)) ;  
break;  
\}  
\}  
return (GetTop(StackD)-'0'); /\* 返回运算结果\*/

[SouthEast]: /images/20220731/a04be0e3b9f54d4a83de057cc5f6f7de.png