数据结构（C语言版）用顺序栈计算表达式

Question

【实验内容与要求】
问题描述：利用栈的基本操作实现一个算术表达式的求值的程序。
基本要求：
（1） 定义栈的顺序存取结构。
（2） 分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。
（3） 定义一个函数用来计算表达式结果，并且可以显示表达式的后缀表示。
（4） 设计一个测试主函数进行测试。

数据结构的形式~~符合的话追加分数~~

Answer 1

#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>

typedef struct
{
char fun;
int grade;
}Functor;
//定义算符栈结构体
Functor FUNCTOR[20];
float NUM[20];
//定义算符栈和对象栈
char ch[100];
int sub=0;
//存放输入流的字符串

float Char_To_Num(){
//将表示数据的字符串转化成数据
int flag=0, i=-1;
float value=0.0;
while((ch[sub]>=48 && ch[sub]<=57) || ch[sub]=='.'){
if(ch[sub]=='.')
flag=1;
else{
if(flag==0) value=value*10+ch[sub]-48;
else{
value=value+( ch[sub]-48 )*pow(10,i);
i--;
}}
sub++;
}
return value;
}

int In_Grade(char c)
{ //算符在栈内时的级别
int g;
switch(c)
{
case '^': g=3;break;
case '*':
case '/':
case '%': g=2;break;
case '+':
case '-': g=1;break;
case '(': g=0;break;
case ')': g=-1;break;
}
return g;
}

int Out_Grade()
{ //算符在栈外时的级别
int g;
switch(ch[sub])
{
case '^': g=4;break;
case '*':
case '/':
case '%': g=2;break;
case '+':
case '-': g=1;break;
case '(': g=4;break;
case ')': g=-1;break;
}
return g;
}

void Error()
{
printf("输入的表达式有误！\n");
printf("\n按任意键退出");
getch();
exit(1);
}

void Calculate(int i, int j)
{
if(i>=2)
{ //判断对象栈中元素个数
switch(FUNCTOR[j-1].fun)
{
case '^': NUM[i-2]=pow(NUM[i-2],NUM[i-1]); break;
case '*': NUM[i-2]=NUM[i-2]*NUM[i-1]; break;
case '/': NUM[i-2]=NUM[i-2]/NUM[i-1]; break;
case '%': NUM[i-2]=int(NUM[i-2])%int(NUM[i-1]); break;
case '+': NUM[i-2]=NUM[i-2]+NUM[i-1]; break;
case '-': NUM[i-2]=NUM[i-2]-NUM[i-1]; break;
}
NUM[i-1]=0;
FUNCTOR[j-1].fun=0;
}
else Error();
//若对象栈若只剩一个数据，则输入的表达式有误
}

float Char_Transform(){
int i=0, j=0, grade, flag=0;
while( ch[sub]!='=' || j!=0 ){
if(ch[sub]=='='){
//输入的字符是否取完
Calculate(i, j);
i--;
j--;}
else{
if(ch[sub]>=48 && ch[sub]<=57){
//判断是否为运算对象
NUM[i++]=Char_To_Num();
if(flag){
NUM[i-1]=-NUM[i-1];
FUNCTOR[j-1].fun=0;
j--;
flag=0;
}}
else{
if(ch[sub]=='%' ||
(ch[sub]>=40 && ch[sub]<=43) ||
ch[sub]=='-' ||ch[sub]=='^' ||
ch[sub]=='/'){
//判断是否为算符
if( FUNCTOR[j-1].fun=='-' &&
FUNCTOR[j-2].fun=='(' &&
ch[sub]==')'){
//判断是否为负数
NUM[i-1]=-NUM[i-1];
FUNCTOR[j-1].fun=0;
FUNCTOR[j-2].fun=0;
j=j-2;
sub++;}
else{
if( FUNCTOR[j-1].fun== '(' && ch[sub]== ')' ){
//括号内表达式计算完后则将左括号从栈中去除
FUNCTOR[j-1].fun=0;
j--;
sub++;}
else{
grade=Out_Grade(); //栈外算符的级别
if(j==0 || grade>FUNCTOR[j-1].grade){
//第一个或级别比栈内算符高的进栈
FUNCTOR[j].fun=ch[sub];
FUNCTOR[j].grade=In_Grade(ch[sub]);
if(j==0 && FUNCTOR[j].fun=='-') flag=1;
j++;
sub++;}
else{
Calculate(i, j);
i--;
j--;
}}}}
else Error();
//表达式中有非算术字符，则表达式有误
}}}
return NUM[i-1];
}

void main()
{
float result;
printf("****************************************\n");
printf("请输入要求解的表达式,并以等号“=”结束:\n");
printf("****************************************\n");
gets(ch);
result=Char_Transform();
printf("%s%.2f\n", ch, result);
printf("\n按任意键退出");
getch();
}