C语言顺序栈实现表达式求值及括号匹配

#include <stdio.h> #include <stdlib.h> #include <string.h>

#define TRUE 1 #define ERROR 0 #define FALSE 1 #define OVERFLOW -2

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10

typedf char SElemType; typedf int Status; char str[80];

//顺序栈的定义 typedf struct{ SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

//顺序栈的初始化 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 TRUE; }

//顺序栈的入栈 Status Push(SqStack &S,char e) { if(S.top - S.base >=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)
exit (OVERFLOW); S.top = S.base + S.stacksize; S.stacksize +=STACKINCREMENT; } *S.top++ =e;
return TRUE; }

//顺序栈的出栈 Status Pop(SqStack &S,int &e){ if(S.top == S.base)
return ERROR;
e = *--S.top ;
return TRUE; }

//取栈顶元素 char GetTop(SqStack S) { if(S.top == S.base ) return ERROR; return *(S.top -1); }

//判断表达式中的括号是否匹配 int Matching(char *str) { SqStack S; InitStack(S);
int flag = 1;
char *ch,x; ch = str;
while(*ch!='#'&&flag) { switch(*ch) { case '[':
case '(': Push(S,*ch); break; case ')':
if(S.top != S.base && GetTop(S)=='(') Pop(S,x);
else flag = 0;
break; case ']':
if(S.top != S.base && GetTop(S)=='[') Pop(S,x);
else flag = 0;
break; } ch++;
} if(S.top == S.base && flag) return 1; else return 0; }

//判断c是否为运算符 int In(SElemType c) { switch(c) { case'+': case'-': case'*': case'/': case'(': case')': case'#': return 1; default: return 0; } }

//判断两符号的优先关系 char Precede(SElemType t1, SElemType t2) { SElemType f; switch(t2) { case'+': case'-': if(t1=='('||t1=='#') f='<'; else f='>'; break; case'': case'/': if(t1==''||t1=='/'||t1==')') f='>'; else f='<'; break; case'(': if(t1==')') { printf("括号不匹配\n"); exit(OVERFLOW); } else f='<'; break; case')': switch(t1) { case'(': f='='; break; case'#': printf("缺乏左括号\n"); exit(OVERFLOW); default: f='>'; } break; case'#': switch(t1) { case'#': f='='; break; case'(': printf("缺乏右括号\n"); exit(OVERFLOW); default: f='>'; } } return f; }

//做四则运算a theta b，返回运算结果 int Operate(int a, char theta, int b) { switch(theta) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; } return a / b; }

char* ConvertToPostfix(char *str) { SqStack OPTR; char postfix = (char)malloc(sizeof(char) * 80); int ch; char theta, x; int j = 0; InitStack(OPTR); Push(OPTR, '#'); ch = str[0]; for(int i = 0; i < strlen(str); i++) { while(ch != '#' || GetTop(OPTR) != '#') { if(!In(ch)) { postfix[j++] = ch; ch = str[++i]; } else { switch(Precede(GetTop(OPTR), ch)) { case '<': Push(OPTR, ch); ch = str[++i]; break; case '>': Pop(OPTR, theta); postfix[j++] = theta; break; case '=': Pop(OPTR, x); ch = str[++i]; break; } } } } postfix[j] = '\0'; return postfix; }

//主函数 int main() { int choice, result; printf("判断表达式括号匹配\n"); printf("1.请输入表达式\n"); printf("2.输出表达式\n"); printf("3.判断表达式的括号是否匹配并计算表达式的值\n"); printf("4.退出\n"); printf("************************************************\n");
while(1) { printf("请输入选择1--4:\n"); scanf("%d",&choice); if(choice > 4 || choice <= 0) { printf("您输入的数据有误!\n"); return 0; } while(choice <= 4) { if(choice == 1) { printf("请输入表达式(以#结尾):\n"); scanf("%s",str); break; } if(choice == 2) { printf("输出表达式:\n"); char *postfix = ConvertToPostfix(str); printf("%s\n", postfix); break; } if(choice == 3) { printf("判断括号是否匹配:\n"); if(Matching(str)) { printf("括号匹配!\n"); result = EvaluateExpression(); printf("表达式的计算结果为:%d\n",result); break; } else { printf("括号匹配不成功!\n"); break; } } if(choice == 4) { printf("退出\n"); return 0; } } } }