#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
typedef int Status;
typedef char SElemType;
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) return NULL;
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return 99;
}
Status Push(SqStack& S, SElemType e) { //入栈
if (S.top - S.base == S.stacksize)
return NULL; //栈满
*S.top++ = e; //元素e压入栈顶,栈顶指针加1
return 99;
}
Status Pop(SqStack& S, SElemType& e) { //出栈
if (S.top == S.base) //栈空
return NULL;
e = *--S.top; //栈顶指针减1,将栈顶元素赋给e
return 99;
}
Status GetTop(SqStack S) { //取栈顶元素
if (S.top != S.base) //栈非空
return *(S.top-1);
}
int In(SElemType e) { //判断读入字符是否为运算符
if (e == '+' || e == '-' || e == '*' || e == '/' || e == '(' || e == ')' || e == '#')
return 99;
else
return NULL;
}
SElemType Precede(SElemType a, SElemType b,SElemType &f) { //比较运算符的优先级
if (a == '+' || a == '-') {
if (b == '+' || b == '-' || b == ')' || b == '#')
f = '>';
else if (b == '*' || b == '/' || b == '(')
f = '<';
}
else if (a == '*' || a == '/') {
if (b == '+' || b == '-' || b == '*' || b == '/' || b == ')' || b == '#')
f = '>';
else if (b == '(')
f = '<';
}
else if (a == '(') {
if (b == '+' || b == '-' || b == '*' || b == '/' || b == '(')
f = '<';
else if (b == ')')
f = '=';
}
else if (a == ')') {
if (b == '+' || b == '-' || b == '*' || b == '/' || b == ')' || b == '#')
f = '>';
}
else if (a == '#') {
if (b == '+' || b == '-' || b == '*' || b == '/' || b == '(')
f = '<';
else if (b == '#')
f = '=';
}
return f;
}
SElemType Operate(SElemType a, SElemType theta, SElemType b,SElemType &e) { //运算
a = a - '\0';
b = b - '\0';
if (theta == '+')
e = a + b + '\0';
else if (theta == '-')
e = a - b + '\0';
else if (theta == '*')
e = a * b + '\0';
else if (theta == '/')
e = a / b + '\0';
return e;
}
int EvaluateExpression() {
SqStack OPND, OPTR;
char c, a, b, theta, x,f,e;
InitStack(OPND); //运算数栈
InitStack(OPTR); //运算符栈
Push(OPTR, '#');
c = getchar();
while (c != '#' || GetTop(OPTR) != '#') {
if (!In(c)) {
Push(OPTR, c);
c = getchar();
}
else
switch (Precede(GetTop(OPTR), c,f)) {
case '<': //栈顶元素优先权低
Push(OPTR, c); c = getchar();
break;
case '=': //脱括号并接收下一字符
Pop(OPTR, x); c = getchar();
break;
case '>': //退栈并将运算结果入栈
Pop(OPTR, theta);
Pop(OPND, b); Pop(OPND, a);
Push(OPND, Operate(a, theta, b,e));
break;
}
}
return GetTop(OPND)-'\0';
}
int main() {
printf("输入表达式:\n");
printf("结果是:%d\n", EvaluateExpression());
}