语言
实现栈的应用中的表达式求值（c语言实现）；
注：?1.实现了双目运算符的计算，例如 >= , <=, || , &&;
????????2.实现了逻辑、算术、关系运算符之间的优先级定义；
? ? ? ? 3.运用链表的形式存储与栈的相关操作；
? ? ? ? 4.实现了两位及两位以上的数字入栈与出栈，
? ? ? ? 5.后续方便你们理解记忆，我定义有关的操作数标志都为_I,因为是int类型，例如操作数栈为Stack_I,定义的运算符因为是char类型，所以后续都为_C,例如Stack_C;
? ? ? ? 6.遇到疑问的话，可滴滴博主； qq 2323388961? vx:15352179826
一.实现思路：
1.用户输入一串表达式，例如3+(5+2)*4+((5||8)>=8)+(3>(2&&4))#，系统将分析输入的表达式，将运算符与运算数分别放到运算符栈Stack_C 和 运算数栈Stack_I;
2.定义相关运算符的优先级，进行入栈与出栈操作；
3.运算符出栈后，进行操作数出栈，然后进行运算，将运算结构压如Stack_I栈
4.最终结果将存在操作数栈中，所以最后遍历输出操作数栈；
二.话不多说，直接上代码（里面有详细注释）
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
typedef struct nood_I
{
int date;
struct nood_I *next; // 运算数链表
}LinkList_I;
typedef struct stack_I
{
LinkList_I *top; // 运算数栈
LinkList_I *bottom;
}Stack_I;
typedef struct nood_C
{
char date;
struct nood_C *next; // 操作符链表
}LinkList_C;
typedef struct stack_C
{
LinkList_C *top; // 操作符栈
LinkList_C *bottom;
}Stack_C;
void init_stack_I(Stack_I *sI); //初始化两个链栈
void init_stack_C(Stack_C *sC);
void push_stack_I(Stack_I *sI,int val); //入栈操作
void push_stack_C(Stack_C *sC,char ch);
void traverse_stack_I(Stack_I *sI); // 遍历两个栈
void traverse_stack_C(Stack_C *sC);
void gettop_stack_C(Stack_C *sC,char *val); // 运算符出栈
void gettop_stack_I(Stack_I *sI,int *val); //数字 出栈
bool judge(char ch); // 判断ch 是否为运算符；
bool judge1(char ch);
char estimate(char t1,char t2); // 比较优先级;
int operate(int a,int b,char ch); //传入两个数据和运算符 进行运算；
int operate_1(int a,int b,char ch,char *arr,int i,Stack_C *sC);
int gettop_I(Stack_I *sI); //数字栈的栈顶元素
char gettop_C(Stack_C *sC); //运算符栈的栈顶元素
void expression_evaluation(void); //表达式求值
char *change(char *a);
int main(void)
{
printf(" 表达式求值\n\n");
expression_evaluation();
return 0;
}
void expression_evaluation()
{
Stack_I sI;
Stack_C sC;
init_stack_I(&sI);
init_stack_C(&sC);
char ch,theta,x,m,d;
char array[1000];
char *p;
int a,b,t,e,i=0;
int isnum=0; // 标志 （判断上一次读取的是否为数字） 用于两位以上的数字进栈
p=array;
printf("\n\n\n\n\n\n\n请输入表达式：（注意：以#结束！）\n");
printf("\n\n输入格式:\n");
printf("1.按照正常的逻辑来输入\n");
printf("2.支持括号运算\n");
printf("3.支持双目运算符， 如>=,<=,&&,||,并且输入时也要完整输入\n");
printf("4.参考输入样例: 3+(5+2)*4+((5||8)>=8)+(3>(2&&4))#\n\n\n");
// getchar();//吸收菜单选项之后的回车键，gets遇见缓冲区的回车会直接读取
gets(array);
change(array);
// puts(array);
push_stack_C(&sC,'#');
ch=array[i];
while(ch!='#'||gettop_C(&sC)!='#') // 第一个条件判断是否输入完毕，第二个条件判断是否运算完毕；
{
if(!judge(ch)) //判断是否为操作符，不是则执行下面操作
{
if(isnum==1)
{
i++;
gettop_stack_I(&sI,&e);
t=ch-'0';
push_stack_I(&sI,e*10+t); // 将栈顶元素拿出和ch进行合并 然后压入栈中；
isnum=1;
ch=array[i];
}
else
{
i++;
push_stack_I(&sI,ch-'0'); //上一次是字符，输入的是个位数，则直接压栈
isnum=1;
ch=array[i];
}
}
else // 读取的是运算符;
{
isnum=0; //进入循环不是 | &
switch(estimate(gettop_C(&sC),ch)) // 判断栈顶元素和ch的优先级关系 函数
{
case '<':
i++; //将当前字符 ch 压入栈sC 读入下一个字符
push_stack_C(&sC,ch);
ch=array[i];
break;
case '>': //弹出运算符栈顶的运算符，弹出数字栈中的数字，进行运算，并且压栈
gettop_stack_C(&sC,&theta);
gettop_stack_I(&sI,&b);
gettop_stack_I(&sI,&a);
if(theta!='j' && theta!='k')
{
push_stack_I(&sI,operate(a,b,theta)); //计算a,b的结果，并且压栈；
}
else
{
push_stack_I(&sI,operate_1(a,b,theta,array,i,&sC)); //计算a,b的结果，并且压栈； 是&& ||
}
break;
case '=':
i++; // 脱括号并接受下一字符
gettop_stack_C(&sC,&x); //将栈中的左括号和ch中的右括号脱去，或者#遇到#
ch=array[i];
break;
}
}
}
// while 结束循环说明栈底只剩于 # ch里面也剩 #
traverse_stack_I(&sI);
}
void init_stack_I(Stack_I *sI)
{
sI->top=(LinkList_I *)malloc(sizeof(LinkList_I));
if(sI->top==NULL)
{
printf("内存分配失败！！\n");
exit(-1);
}
else
{
sI->bottom=sI->top;
sI->top->next=NULL;
}
}
// 初始化 运算符 栈
void init_stack_C(Stack_C *sC)
{
sC->top=(LinkList_C *)malloc(sizeof(LinkList_C));
if(sC->top==NULL)
{
printf("内存分配失败！！！\n");
exit(-1);
}
else
{
sC->bottom=sC->top;
sC->top->next=NULL;
}
}
// 数字栈入栈
void push_stack_I(Stack_I *sI,int val)
{
LinkList_I *p;
p=(LinkList_I *)malloc(sizeof(LinkList_I));
p->date=val;
p->next=sI->top;
sI->top=p;
}
//字符栈入栈
void push_stack_C(Stack_C *sC,char ch)
{
LinkList_C *p;
p=(LinkList_C *)malloc(sizeof(LinkList_C));
p->date=ch;
p->next=sC->top;
sC->top=p;
}
void traverse_stack_I(Stack_I *sI)
{
LinkList_I *p;
p=sI->top;
while(p->next!=NULL)
{
printf("%d ",p->date);
p=p->next;
}
}
void traverse_stack_C(Stack_C *sC)
{
LinkList_C *p;
p=sC->top;
while(p->next!=NULL)
{
printf("%c ",p->date);
p=p->next;
}
}
// 判断是否为运算符
bool judge(char ch)
{
switch(ch)
{
case '+':
return true;
case '-':
return true;
case '*':
return true;
case '/':
return true;
case '(':
return true;
case ')':
return true;
case '#':
return true;
case '>':
return true;
case '<':
return true;
case '!':
return true;
case '=':
return true;
case '|':
return true;
case '&':
return true;
case 'd':
return true;
case 'x':
return true;
case 'j':
return true;
case 'k':
return true;
default :
return false;
}
}
bool judge1(char ch)
{
switch(ch)
{
case '=':
return true;
case '|':
return true;
case '&':
return true;
default :
return false;
}
}
//判断 两个运算符的优先级 如果t1 > t2 数字栈出栈，字符栈出栈，完成运算 t2为后入栈元素
char estimate(char t1,char t2)
{
char f;
switch(t2)
{
case '-':
if(t1=='('||t1=='#')
f='<';
else f='>';
break;
case '+':
if(t1=='('||t1=='#')
f='<';
else f='>';
break;
case '*':
if(t1=='('||t1=='#'||t1=='+'||t1=='-')
f='<';
else f='>';
break;
case '/':
if(t1=='('||t1=='#'||t1=='+'||t1=='-')
f='<';
else f='>';
break;
case '(':
if(t1==')')
f='=';
else f='<';
break;
case ')':
if(t1=='('||t1=='#')
f='=';
else f='>';
break;
case '#':
if(t1=='('||t1=='#')
f='=';
else f='>';
break;
case '>':
if(t1=='('||t1=='#')
f='<';
else
f='>';
break;
case '<':
if(t1=='('||t1=='#')
f='<';
else
f='>';
break;
case '!':
if(t1=='('||t1=='#')
f='<';
else
f='>';
break;
case 'd':
if(t1=='('||t1=='#')
f='<';
else
f='>';
break;
case 'x':
if(t1=='('||t1=='#')
f='<';
else
f='>';
break;
case 'j': // ||
if(t1=='('||t1=='#')
f='<';
else
f='>';
break;
case 'k': // &&
if(t1=='('||t1=='#')
f='<';
else
f='>';
break;
}
return f;
}
//传入两个数据和运算符 进行运算；
int operate(int a,int b,char ch)
{
int sum=0;
switch(ch)
{
case '+':
sum=a+b;
break;
case'-':
sum=a-b;
break;
case '*':
sum=a*b;
break;
case '/':
sum=a/b;
break;
case '>':
if(a>b)
sum=1;
else
sum=0;
break;
case '<':
if(a>b)
sum=0;
else
sum=1;
break;
case '!':
if(a==b)
sum=0;
else
sum=1;
break;
case 'd':
if(a>=b)
sum=1;
else
sum=0;
break;
case 'x':
if(a<=b)
sum=1;
else
sum=0;
break;
}
return sum;
}
//运算符为 || &&
int operate_1(int a,int b,char ch,char *arr,int i,Stack_C *ssC)
{
int sum=0;
LinkList_C *ph;
ph=ssC->top->next;
switch(ch)
{
case 'j': // ||
char *p;
p=arr;
if(*(p+i+1)=='>'||*(p+i+1)=='d')
{
if(a>b)
{
sum=a;
}
else
sum=b;
}
if(*(p+i+1)=='<'||*(p+i+1)=='x')
{
if(a>b)
{
sum=b;
}
else
sum=a;
}
if(ph->date=='>'||ph->date=='d')
{
if(a>b)
{
sum=b;
}
else
sum=a;
}
if(ph->date=='<'||ph->date=='x')
{
if(a>b)
{
sum=a;
}
else
sum=b;
}
break;
case 'k': // &&
char *pk;
pk=arr;
if(*(pk+i+1)=='>'||*(pk+i+1)=='d')
{
if(a>b)
{
sum=b;
}
else
sum=a;
}
if(*(pk+i+1)=='<'||*(pk+i+1)=='x')
{
if(a>b)
{
sum=a;
}
else
sum=b;
}
if(ph->date=='>'||ph->date=='d')
{
if(a>b)
{
sum=a;
}
else
sum=b;
}
if(ph->date=='<'||ph->date=='x')
{
if(a>b)
{
sum=b;
}
else
sum=a;
}
break;
}
return sum;
}
//运算符出栈
void gettop_stack_C(Stack_C *sC,char *val)
{
LinkList_C *r;
r=sC->top;
*val=r->date;
sC->top=r->next;
free(r);
r=NULL;
}
//数字 出栈
void gettop_stack_I(Stack_I *sI,int *val)
{
LinkList_I *r;
r=sI->top;
*val=r->date;
sI->top=r->next;
free(r);
r=NULL;
}
//数字栈的栈顶元素
int gettop_I(Stack_I *sI)
{
LinkList_I *p;
p=sI->top;
return p->date;
}
//运算符栈的栈顶元素
char gettop_C(Stack_C *sC)
{
LinkList_C *p;
p=sC->top;
return p->date;
}
char *change(char *a) //将双目运算符 && || >= <= 转换成相应的单个字符对应，方便入栈出栈，
{
int i,j;
for(i=0;a[i]!='\0';i++)
{
if(a[i]=='>'&&a[i+1]=='=')
{
int k;
a[i]='d';
for(k=i+1;a[k]!='\0';k++)
{
a[k]=a[k+1];
}
}
if(a[i]=='<'&&a[i+1]=='=')
{
int k;
a[i]='x';
for(k=i+1;a[k]!='\0';k++)
{
a[k]=a[k+1];
}
}
if(a[i]=='|'&&a[i+1]=='|')
{
int k;
a[i]='j';
for(k=i+1;a[k]!='\0';k++)
{
a[k]=a[k+1];
}
}
if(a[i]=='&'&&a[i+1]=='&')
{
int k;
a[i]='k';
for(k=i+1;a[k]!='\0';k++)
{
a[k]=a[k+1];
}
}
}
}三.程序结果展示：
