算术表达式求值（有括号）

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include<windows.h>
typedef struct _expr{
char expression[40];
char *top;
char *base;
}expr;
char chars[7][7]={
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=','$',
'>','>','>','>','$','>','>',
'<','<','<','<','<','$','='
};//符号优先级比较表
char ch[] = {'+','-','*','/','(',')','#'};
typedef struct _optr{
char operatar[10];
char *base;
char *top;
}optr;//运算符栈
typedef struct _oprd{
int data[10];
int *top;
int *base;
}oprd;//操作数栈
int get_line( expr *L );
int init_line( expr *L );
int init_optr( optr *x );
int init_oprd( oprd *x );
int empty_optr( optr *x );
int exchage_char_num( optr *x );
int get_num( char c );
int compare(char row , char cal);
int cal_experssion( expr *L );
void push_optr( optr *x , char ch );
void push_oprd( oprd *x , int data );
void pop_optr( optr *x );
void pop_oprd( oprd *x );
void get_base( expr *L , char *a );
int main()
{
system("color f5");
expr express;
init_line(&express);
get_line(&express);
printf("%d\n",cal_experssion(&express));
return 0;
}
int cal_experssion(expr *L)//运算表达式
{
optr OPTR,temp;
oprd OPRD;
int i,data1,data2;
char a,b;
init_optr(&OPTR);
init_oprd(&OPRD);
init_optr(&temp);//临时符号栈，便于将读取的数值字符转化为数字
push_optr(&OPTR,'#');
get_base(L , &a);
while(a != '#' || *(OPTR.top-1) != '#')
{
if(a >= '0' && a <= '9')
{
push_optr(&temp ,a);
get_base(L, &a);
}
else
{
if( !empty_optr( &temp) )
push_oprd( &OPRD , exchage_char_num(&temp));//将数值字符转换为数字存入操作数栈
b = *(OPTR.top-1);
i = compare(b , a);
while(i == 1)//后面运算符优先级低
{
data1 = *OPRD.top;//取出栈顶操作数
pop_oprd(&OPRD);//出栈
data2 = *OPRD.top;//取出栈顶操作数
pop_oprd(&OPRD);//出栈
switch(get_num(b))
{
case 0://加法运算
push_oprd(&OPRD,data2+data1);
pop_optr(&OPTR);
break;
case 1://减法运算
push_oprd(&OPRD,data2-data1);
pop_optr(&OPTR);
break;
case 2://乘法运算
push_oprd(&OPRD,data2*data1);
pop_optr(&OPTR);
break;
case 3://除法运算
push_oprd(&OPRD,data2/data1);
pop_optr(&OPTR);
break;
}
b = *(OPTR.top-1);
i = compare(b,a);
}
if(i == 2 && a != '#')
{
push_optr(&OPTR,a);
get_base(L , &a);
}
if(i ==3 && a != '#')
{
pop_optr(&OPTR);
get_base(L,&a);
}
}
}
return *OPRD.top;
}
int compare(char row , char cal)//比较符号的优先级
{
int i,j;
i= get_num(row);
j = get_num(cal);
if(chars[i][j] == '>')
return 1;
else if(chars[i][j] == '<')
return 2;
else if(chars[i][j] == '=')
return 3;
else if(chars[i][j] == '$')
{
printf("表达式错误！");
exit(0);
}
}
int get_num( char c )//判断是什么符号
{
int i=0;
while(c != ch[i]) i++;
return i;
}
int exchage_char_num( optr *x )
{
int i;
i = atoi(x->operatar);
init_optr(x);
return i;
}
int empty_optr( optr *x )//判断操作数栈是否为空
{
if(x->base == x->top)
return 1;
else if(x->base != x->top )
return 0;
}
void get_base( expr *L , char *a )//取表达式的第一个元素
{
*a = *L->base;
 L->base++;
}
void push_oprd(oprd *x, int data)//操作数入栈
{
x->top++;
*(x->top) = data;
}
void push_optr( optr *x , char ch )//符号入栈
{
*(x->top) = ch;
x->top++;
*(x->top) = '\0';
}
void pop_oprd( oprd *x )//操作数出栈
{
*(x->top) = 0;
x->top--;
}
void pop_optr( optr *x )//符号出栈
{
x->top--;
*(x->top) = '\0';
}
int init_oprd( oprd *x )//初始化操作数栈
{
x->base = x->top = x->data;
x->data[0] = 0;
return 0;
}
int init_optr( optr *x )//初始化字符栈
{
x->base = x->top = x->operatar;
x->operatar[0] = '\0';
return 0;
}
int init_line( expr *L )
{
L->base = L->top = NULL;
L->expression[0] = '\0';
return 0;
}
int get_line( expr *L )//在表达式最后面加上"#"
{
int i;
gets(L->expression);
i = strlen(L->expression);
L->expression[i] = '#';
L->expression[i+1] = '\0';
L->top = &L->expression[i];
L->base = L->expression;
return 0;
}