#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OK 1
#define ERROR 0
#define OVERLOW -2
const char oper[7] = {'+' , '-' , '*' , '/' , '(' , ')', '#',};
typedef char SElem;
typedef int status;
typedef struct Snode{
int data ;
struct Snode* next ;
}Snode,*LinkStack;
status InitStack (LinkStack s){//链栈的初始化
(s)=NULL;
return OK;
}
int stackempty (LinkStack s)//判空
{
if(!s)
return OK;
return ERROR;
}
status Push (LinkStack *s, SElem e)//入栈
{
Snode *p = (LinkStack )malloc(sizeof(LinkStack));
if( !p )
{
return OVERLOW;
}
p->data = e;
p->next = (*s);
(*s) = p;
return OK;
}
status Pop (LinkStack *s,SElem *e)//弹出栈
{
Snode *p;
if( !(*s) )
return ERROR;
(*e) = (*s)->data;
p = (*s);
(*s) = (*s) ->next;
free(p);
return OK;
}
status GetTop(LinkStack *s)//取数据
{
if( !(*s) )
return ERROR;
return (*s)->data;
}
int In( char ch)//判断ch是否为运算符
{
int i;
for( i = 0 ; i < 7 ; i++ )
{
if ( ch == oper [i] )
return OK;
}
return ERROR ;
}
char Precede (char theta1, char theta2)//判断运算符优先级
{
if((theta1 == '(' && theta2 == ')' ) || (theta1 == '#' && theta2 =='#' ))
{
return '=' ;
}
else if (theta1 == '(' || theta1 == '#' || theta2 == '(' || (theta1 == '+' || theta1 == '-' )
&& (theta2 == '*' || theta2 == '/' ))
{
return '<' ;//theta1的运算符优先级小于theta2
}
else return '>' ;
}
char Operate (char first , char theta ,char second)//计算两数运算的结果
{
switch (theta){
case '+':
return (first -'0') + (second -'0') + 48;
case '-':
return (first -'0') - (second -'0') + 48;
case '*':
return (first - '0') * (second -'0') + 48;
case '/':
return (first -'0') / (second -'0') + 48;
}
return 0;
}
char EvaluateExpression() {//算术表达式求值的算符优先算法,设OPTR和OPND分别为运算符栈和操作数栈
LinkStack OPTR, OPND;//POTR寄存运算符,OPND寄存操作数据或运算结果
char ch, theta, a, b, x, top;
InitStack(OPND);
InitStack(OPTR);
Push(&OPTR, '#'); //将表达式起始符“#”压入OPTR栈
scanf("%s",ch);
while (ch != '#' || (GetTop(&OPTR) != '#')) //表达式没有扫描完毕或OPTR的栈顶元素不为“#”
{
if (!In(ch)) {
Push(&OPND, ch);
scanf("%s",ch);
} //ch不是运算符则进OPND栈
else
switch (Precede(GetTop(&OPTR), ch)) //比较OPTR的栈顶元素和ch的优先级
{
case '<':
Push(&OPTR, ch);
scanf("%s",ch); //当前字符ch压入OPTR栈,读入下一字符ch
break;
case '>':
Pop(&OPTR, &theta); //弹出OPTR栈顶的运算符
Pop(&OPND, &b);
Pop(&OPND, &a); //弹出OPND栈顶的两个运算数
Push(&OPND, Operate(a, theta, b)); //将运算结果压入OPND栈
break;
case '=': //OPTR的栈顶元素是“(”且ch是“)”
Pop(&OPTR, &x);
scanf("%s",ch); //弹出OPTR栈顶的“(”,读入下一字符ch
break;
}
}
return GetTop(&OPND); //OPND栈顶元素即为表达式求值结果
}
int menu() {
int c;
printf("0-9以内的多项式计算\n");
printf("1.计算\n");
printf("0.退出\n");
printf("选择:\n");
scanf("%d",&c);
return c;
}
int main() {
while (1) {
switch (menu()) {
case 1: {
printf("请输入要计算的表达式(操作数和结果都在0-9的范围内,以#结束):\n");
char res = EvaluateExpression();//算法3.22 表达式求值
printf("计算结果为:%d\n",(res-48));
}
break;
case 0:
printf("退出成功\n");
exit(0);
default:
break;
}
}
}