尝试实现一个c语言的功能,需要输入一个表达式输出对应结果,包括加减乘除乘方,中小括号。
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#define ARGC_CNT 2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define OVERFLOW 0
#define ERROR 0
typedef double Status;
typedef double SElemType; //操作数
typedef char status;
typedef char selemType; //运算符
typedef struct {
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;//操作数栈
typedef struct {
selemType* base;
selemType* top;
int stacksize;
}sqStack;//运算符栈
char prior[10][10] = {
{'>','>','<','<','<','<','>','<','>','>'},
{'>','>','<','<','<','<','>','<','>','>'},
{'>','>','>','>','<','<','>','<','>','>'},
{'>','>','>','>','<','<','>','<','>','>'},
{'>','>','>','>','>','<','>','<','>','>'},
{'<','<','<','<','<','<','=','>','?','?'},
{'>','>','>','>','>','?','>','?','>','>'},
{'<','<','<','<','<','<','?','<','=','?'},
{'>','>','>','>','>','?','<','?','>','>'},
{'<','<','<','<','<','<','?','<','?','='} };
char OPSET[10] = { '+','-','*','/','^','(',')','[',']','#'};
Status InitStack(SqStack* s)//初始化操作数栈
{
s->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!s->base)
exit(OVERFLOW);
s->top = s->base;
s->stacksize = STACK_INIT_SIZE;
return OK;
}
status initStack(sqStack* s)//初始化运算符栈
{
s->base = (selemType*)malloc(STACK_INIT_SIZE * sizeof(selemType));
if (!s->base)
exit(OVERFLOW);
s->top = s->base;
s->stacksize = STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack* s, SElemType c)//入栈
{
if ((s->top - s->base) >= s->stacksize)
{
s->base = (SElemType*)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElemType));
if (!s->base)
exit(OVERFLOW);
s->stacksize += STACKINCREMENT;
}
*(s->top)++ = c;
return OK;
}
status push(sqStack* s, selemType c)//入栈
{
if ((s->top - s->base) >= s->stacksize)
{
s->base = (selemType*)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(selemType));
if (!s->base)
exit(OVERFLOW);
s->stacksize += STACKINCREMENT;
}
*(s->top)++ = c;
return OK;
}
Status GetTop(SqStack* s)//取栈顶元素
{
SElemType e;
if (s->base == s->top)
{
printf("ERROR_02");//操作数栈为空,即重复运算符
exit(0);
}
e = *(s->top - 1);
return e;
}
status getTop(sqStack* s)//取栈顶元素
{
selemType e;
if (s->base == s->top)
{
printf("ERROR_02");//运算符栈为空
exit(0);
}
e = *(s->top - 1);
return e;
}
int In(char c)//判断是否为运算符
{
if (c=='+'||c=='-'||c=='*'||c=='/'||c=='^'||c=='('||c==')'||c=='['||c==']')
{
return OK;
}
else
{
return ERROR;
}
}
status precede(char a, char b)//判断优先级函数
{
int i = 0, j = 0;
while (a != OPSET[i]) { i++; }
while (b != OPSET[j]) { j++; }
if (prior[i][j] == '?') {
printf("ERROR_02");//输入表达式错误
exit(0);
}
return prior[i][j];
}
Status Pop(SqStack* s)//脱括号函数
{
SElemType e;
if (s->base == s->top)
return ERROR;
e = *--(s->top);
return e;
}
status pop(sqStack* s)
{
int e;
if (s->base == s->top)
return ERROR;
e = *--(s->top);
return e;
}
Status Opereta(double a, char b, double c)//运算函数
{
switch (b)
{
case '+':
return a + c;
case '-':
return a - c;
case '*':
return a * c;
case '/':
if(c==0)
{
printf("ERROR_03");//除数为0
exit(0);
}
else
{
return a / c;
}
case '^':
return pow(a, c);
}
}
int Check(char* S) {
int i;
for (i = 0; i < strlen(S); i++) {
if (S[i] >= '0' && S[i] <= '9')continue;
if (S[i] == '(' || S[i] == ')' || S[i]=='[' || S[i]==']' || S[i] == '*' || S[i] == '/' || S[i] == '+' || S[i] == '-' || S[i] == '.')continue;
return ERROR;
}
return OK;
}//检查函数,用来检查输入的表达式的操作数和运算符的合法性
double EvaluateExpression(char* MyExpression)
{//算术表达式求值的算符优先算法。
if (Check(MyExpression) == 0) {
printf("ERROR_02");//输入的表达式不合法
exit(0);
}
//设OPTR和OPND分别为运算符栈和运算数栈
sqStack OPTR;//运算符栈,字符元素
SqStack OPND;//运算数栈,实数元素
char TempData[100];
char DR[2];
DR[1] = '\0';
double data, a, b;
int l = 0;
char theta;
initStack(&OPTR);
push(&OPTR, '#');
InitStack(&OPND);
TempData[0] = '\0';
while (MyExpression[l]!='#'||getTop(&OPTR)!='#')
{
if (!In(MyExpression[l]))//不是运算符则进栈
{
DR[0]=MyExpression[l];
strcat(TempData,DR);
l++;
if (In(MyExpression[l]))//是运算符时
{
data = atof(TempData);
Push(&OPND, data);
TempData[0] = '\0';
}
}
else
{
switch (precede(getTop(&OPTR),MyExpression[l]))
{
case '<':
push(&OPTR, MyExpression[l]);
l++;
break;
case '=':
pop(&OPTR);
l++;
break;
case '>':
a = Pop(&OPND);
b = Pop(&OPND);
theta = pop(&OPTR);
Push(&OPND, Opereta(b, theta, a));
break;
}
}
}
return GetTop(&OPND);
}
int main()
{
char*argv;
scanf("%s",argv);
printf("%g", EvaluateExpression(argv));
return 0;
}
输入1+2,结果为栈缓冲区溢出
输入后,判断是否有非法字符,如果合法进行运算。依靠栈堆叠来进行,同时判断运算符优先级。最后如果可以正常输出结果则输出,否则输出"ERROR"。
能够正常实现功能,首先希望可以定位出现问题的位置。