Question

如何用C语言数据结构的格式实现简单的算术表达式求值程序

要求：输入一个算术表达式，其中包含有数字，加、减、乘、除号、括号，能根据四则运算法则计算出正确结果。

Answer 1

用栈把中缀表达式(输入的式子）按优先级转为后缀表达式（逆波兰式，即运算符在前，操作数在后），再利用栈变计算边保存结果用于下一步计算，最后算出式子的答案

以下代码输入一个式子（以 = 作为输入结束标志），输出结果，负数如-3用0-3表示，支持高位运算
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <malloc.h>

#define OK 1
#define ERROR -1
typedef char SElemType;

typedef char Status;
#define STACK_INIT_SIZE 100000
#define STACKINCREMENT 2

struct SqStack
{
SElemType *base;
SElemType *top;
int stacksize;
};

struct SqStack1
{
int *base;
int *top;
int stacksize;
};

SqStack OPTR;
SqStack1 OPND;

char Precede(char c1,char c2)
{
if(c1=='+' || c1=='-')
{
if(c2=='+' || c2=='-' || c2==')' || c2=='=') return '>';
else return '<';
}
else if(c1=='*' || c1=='/')
{
if(c2=='(') return '<';
else return '>';
}
else if(c1=='(')
{
if(c2==')') return '=';
else return '<';
}
else if(c1==')') return '>';
else if(c1=='=')
{
if(c2=='=') return '=';
else return '<';
}
else return '\0';
}

int In(char c)
{
if(c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')' || c=='=')
return 1;
else return 0;
}

int Operrate(int m,char b,int n)
{
switch(b)
{
case '+':return m+n;
case '-':return m-n;
case '*':return m*n;
case '/':return m/n;
}
return 0;
}

//操作数

int InitStack1(SqStack1 &S)
{
S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}

int Push1(SqStack1 &S,int e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));

S.top=S.base+S.stacksize;
S.stacksize=S.stacksize+STACKINCREMENT;
}
*S.top++=e;
return OK;
}

int Pop1(SqStack1 &S,int &e)
{
if(S.top==S.base) return ERROR;
e=* --S.top;
return OK;
}

int GetTop1(SqStack1 S)
{
if(S.top==S.base) return ERROR;
return *(S.top-1);
}

//算符

int InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}

int Push(SqStack &S,SElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

S.top=S.base+S.stacksize;
S.stacksize=S.stacksize+STACKINCREMENT;
}
*S.top++=e;
return OK;
}

int Pop(SqStack &S,SElemType &e)
{
if(S.top==S.base) return ERROR;
e=* --S.top;
return OK;
}

Status GetTop(SqStack S)
{
if(S.top==S.base) return ERROR;
return *(S.top-1);
}

int Calculate()
{
char c,theta,p;
int a,b,i=0,ans,x;
InitStack(OPTR);
Push(OPTR,'=');
InitStack1(OPND);
c=getchar();
while(c!='=' || GetTop(OPTR)!='=')
{
if(!In(c) && c>='0' && c<='9')
{
Push1(OPND,c-'0');
c=getchar();

while(c>='0' && c<='9')
{
Pop1(OPND,x);
Push1(OPND,x*10+c-'0');
c=getchar();
}
}
else if(In(c))
{
switch(Precede(GetTop(OPTR),c))
{
case '<':
Push(OPTR,c);
c=getchar();
break;
case '=':
Pop(OPTR,p);
c=getchar();
break;
case '>':
Pop(OPTR,theta);
Pop1(OPND,b);
Pop1(OPND,a);

ans=Operrate(a,theta,b);
Push1(OPND,ans);
break;
}
}
else
{
c=getchar();
}
}
return GetTop1(OPND);
}

int main()
{
int ans;
ans=Calculate();
printf("%d\n",ans);
return 0;
}

Answer 2

#include<cstdio>
#include<malloc.h>
#define NULL 0
typedef struct node{
char date;
struct node *next;
}SNode;

SNode *InitStack(){
SNode *top;
top=(SNode *)malloc(sizeof(SNode));
top->next=NULL;
return top;
}
void PushOptr(SNode *top,char x){
SNode *p;
p=(SNode *)malloc(sizeof(SNode));
p->date=x;
p->next=top->next;
top->next=p;

}
char PopOptr(SNode *top){
SNode *p;
char x;
if(top==NULL)
return NULL;
p=top->next;
x=p->date;
top->next=p->next;
free(p);
return x;
}
void PushOpnd(SNode *top,char x){
SNode *p;
p=(SNode *)malloc(sizeof(SNode));
p->date=x;
p->next=top->next;
top->next=p;
}
char PopOpnd(SNode *top){
SNode *p;
char x;
if(top==NULL)
return NULL;
p=top->next;
x=p->date;
top->next=p->next;
free(p);
return x;
}
char GetTop(SNode *top){

return (top->next)->date;
}
int In(char c){
int n;
switch(c){
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
case '#':n=1;break;
default:n=0;break;
}
return n;
}
char Precede(char x,char y){
int i,j;
int form[7][7]={{1,1,-1,-1,-1,1,1},{1,1,-1,-1,-1,1,1},{1,1,1,1,-1,1,1},{1,1,1,1,-1,1,1},{-1,-1,-1,-1,-1,0,2},{1,1,1,1,2,1,1},{-1,-1,-1,-1,-1,2,0}};
switch(x){
case '+':i=0;break;
case '-':i=1;break;
case '*':i=2;break;
case '/':i=3;break;
case '(':i=4;break;
case ')':i=5;break;
case '#':i=6;break;
}
switch(y){
case '+':j=0;break;
case '-':j=1;break;
case '*':j=2;break;
case '/':j=3;break;
case '(':j=4;break;
case ')':j=5;break;
case '#':j=6;break;
}
if(form[i][j]==1)
return '>';
else
if(form[i][j]==-1)
return '<';
else
return '=';

}
int Operate(char x,char z,char y){
int a=x-'0',b=y-'0';
switch(z){
case '+':return a+b;
case '-':return a-b;
case '*':return a*b;
case '/':return a/b;
}
}
char Eval_Exp(){
char a,b,c,r,f,z;
int result;
SNode *top[2];
top[0]=InitStack();
PushOptr(top[0],'#');
top[1]=InitStack();
c=getchar();
while(c!='#'||(GetTop(top[0]))!='#'){
if(!In(c)){
PushOpnd(top[1],c);
c=getchar();
}
else{
r=Precede(GetTop(top[0]),c);
switch(r){
case '<':PushOptr(top[0],c);
c=getchar();
break;
case '=':PopOptr(top[0]);
c=getchar();
break;
case '>':b=PopOptr(top[0]);
a=PopOpnd(top[1]);
z=PopOpnd(top[1]);
result=Operate(z,b,a);
f=result+'0';
PushOpnd(top[1],f);
break;
}

}
}
return f;
}
void main(){
char result;
result=Eval_Exp();
printf("%d\n",result-'0');

}

Answer 3

简单用逆波兰就可以实现了