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

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

//顺序栈的定义 typedef 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 EvaluateExpression() { SqStack OPND,OPTR; int ch; int a, b; char theta, x; InitStack(OPND); InitStack(OPTR); Push(OPTR,'#'); ch = str[0]; for(int i = 0; i < strlen(str); i++) { while(ch != '#' || GetTop(OPTR) != '#') { if(!In(ch)) { Push(OPND, ch - '0'); ch = str[++i]; } else { switch(Precede(GetTop(OPTR), ch)) { case '<': Push(OPTR, ch); ch = str[++i]; break; case '>': Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b)); break; case '=': Pop(OPTR, x); ch = str[++i]; break; } } } } return GetTop(OPND); }

//主函数 int main() { int choice,result; int i; 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'); printf('%s\n',str); break; } if(choice == 3) { printf('判断括号是否匹配:\n'); if(Matching(str)) { printf('括号匹配!\n'); printf('后缀表达式:\n'); SqStack S; InitStack(S); char postfix[80]; int index = 0; for(i = 0; i < strlen(str); i++) { if(!In(str[i])) { postfix[index++] = str[i]; } else { if(GetTop(S) != '#' && Precede(GetTop(S), str[i]) == '>') { postfix[index++] = GetTop(S); Pop(S, i); } Push(S, str[i]); } } while(GetTop(S) != '#') { postfix[index++] = GetTop(S); Pop(S, i); } postfix[index] = '\0'; printf('%s\n', postfix);

                result = EvaluateExpression();
                printf('表达式的计算结果为:%d\n',result);
                break;
            }
            else
            {
                printf('括号匹配不成功!\n');
                break;
            }
        }
        if(choice == 4)
        {
            printf('退出\n');
            return 0;
        }
    }
}