中缀表达式3 + 4/（25 -（6+15））* 8转换为后缀表达式

中缀表达式3 + 4/（25 -（6+15））* 8转换为后缀表达式

该问题的求解可以分为两部分：
1、中缀表达式到后缀表达式的转换；
2、后缀表达式的计算；

具体代码如下：

#include
#define StackSize 100
#define QueueSize 100

typedef char DataType;
typedef struct{
char data[100];
int front, rear;
}SeqQueue; // 定义队列类型

void InitQueue(SeqQueue *Q) // 初始化队列
{
Q->front = 0;
Q->rear = 0;
}

int QueueEmpty(SeqQueue *Q) // 判空队列
{
return Q->rear == Q->front;
}

void EnQueue(SeqQueue *Q, DataType x) // 入队列
{
if ((Q->rear + 1) % QueueSize == Q->front)
{
cout << "Queue overflow" << endl;
}
else
{
Q->data[Q->rear] = x;
Q->rear = (Q->rear + 1) % QueueSize;
}
}

DataType DeQueue(SeqQueue *Q) // 出队列
{
if (Q->rear == Q->front)
{
cout << "Queue empty" << endl;
}
else
{
DataType temp = Q->data[Q->front];
Q->front = (Q->front + 1) % QueueSize;
return temp;
}
}


typedef struct{
DataType data[100];
int top;
}SeqStack; //栈类型的定义

void InitStack(SeqStack *S) //初始化栈
{
S->top = 1;
}

void Push(SeqStack * S, DataType d) // 入栈
{
if(S->top == StackSize - 1)
{
cout << "stack overflow" << endl;
}
else
{
S->top = S->top + 1;
S->data[S->top] = d;
}
}

DataType Pop(SeqStack * S) // 出栈
{
if (S->top == -1)
{
cout << "stack underflow" << endl;
}
else
return S->data[S->top--];
}

DataType GetTop(SeqStack *S) // 取栈顶元素
{
if (S->top == -1)
{
cout << "stack empty" << endl;
}
else
{
return S->data[S->top];
}
}

//求运算符优先级
int Priority(DataType op)
{
switch (op)
{
case '(':
case '#': return (0);
case '-':
case '+': return (1);
case '*':
case '/': return (2);
}
}

void CTPostExp(SeqQueue *Q)
{
SeqStack OS; // 运算符栈
char c,t;
SeqStack *S;
S = &OS;
InitStack(S);
Push(S,'#'); // 压入栈底元素'#'
do // 扫描表达式
{
c = getchar();
switch (c)
{
case ' ':
break; // 去除空格
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
EnQueue(Q, c); break;
case '(': Push(S, c); break;
case ')':
case '#':
do {
t = Pop(S);
if(t != '(' && t != '#')
EnQueue(Q, t);
}while (t != '(' && S->top != 1);
break;
case '+':
case '-':
case '*':
case '/':
while(Priority(c) <= Priority(GetTop(S)))
{
t = Pop(S);
EnQueue(Q, t);
}
Push(S, c);
break;

}
}while(c != '#'); // 以'#'号结束表达式扫描
}

// 计算后缀表达式
int CPostExp(SeqQueue *Q)
{
SeqStack VS, *S;
char ch;
int x,y;
S = &VS;
InitStack(S);
while(!QueueEmpty(Q))
{
ch = DeQueue(Q);
if(ch >= '0' && ch <= '9')
{
Push(S, ch - '0');
}
else
{
y = Pop(S);
x = Pop(S);
switch (ch)
{
case '+' : Push(S, x + y); break;
case '-' : Push(S, x - y); break;
case '*' : Push(S, x * y); break;
case '/' : Push(S, x / y); break;
}
}
}
return GetTop(S);
}

int main()
{
SeqQueue *Q;
SeqQueue PostQ; //定义队列，存放后缀表达式
Q = &PostQ;
InitQueue(Q); //初始化队列
cout << "请输入数学表达式（以'#'结束):\n";
CTPostExp(Q);
// 计算后缀表达式
cout << "该表达式的值为: " << CPostExp(Q) << endl;
return 0;
}

3 4 25 6 15 + - 8 * / +

我写的计算器,用的中缀变后缀,可以进行+ - * / ^浮点运算 具有很强容错能力 #define maxsize 32 #define error(); printf("Expression error!");return 0; typedef float eletype; typedef struct{ eletype data[maxsize]; int top; }stack; stack StackO,StackN; void Initstack(stack *); eletype Push(stack *,eletype); eletype Pop(stack *); eletype Empty(stack *); eletype Full(stack *); eletype Gettop(stack *); char In(char); char Proceed(char ,char); eletype Operate(eletype ,char,eletype); eletype atof(char *); eletype cheng(eletype,eletype); eletype Evalexpres(stack *); eletype panduan(char ); void Initstack(stack *sp){ sp->top=-1; } eletype Push(stack *sp,eletype data){ if(Full(sp))return 0; sp->top++; sp->data[sp->top]=data; return 1; } eletype Pop(stack *sp){ if(Empty(sp))return 0; return sp->data[sp->top--]; } eletype Empty(stack *sp){ return sp->top==-1; } eletype Full(stack *sp){ return sp->top+1==maxsize; } eletype Gettop(stack *sp){ if(Empty(sp))return 0; return sp->data[sp->top]; } char In(char c){ char *str="+-*/^()="; int i; for(i=0;i<8;i++) if(str[i]==c) return 1; return 0; } char Proceed(char a,char b){ char str[8][8]={">><<<<>>",">><<<<>>",">>>><<>>",">>>><<>>", ">>>>><>>","<<<<<<= ",">>>>> >>","<<<<<< ="}; char str1[8]="+-*/^()="; int i; for(i=0;i<8;i++) { if(str1[i]==a)a=i;if(str1[i]==b)b=i; } return str[a][b]; } eletype Operate(eletype a,char r,eletype b){ eletype sum; switch(r){ case '+': sum=a+b;break; case '-': sum=b-a;break; case '*': sum=a*b;break; case '/': sum=b/a;break; case '^': sum=cheng(a,b);break; } return sum; } eletype atof(char *c){ eletype f; sscanf(c,"%f",&f); return f; } eletype cheng(eletype a,eletype b){ eletype sum=b; while(a-1){ sum*=b;a--; } return sum; } eletype panduan(char c){ int a,b; char *s="+-*/^()=0123456789."; for(a=0;s[a];a++) if(c==s[a])return 1; return 0; } eletype Evalexpres(stack *sp){ int l,ll,x,y,m,n,i=0,j=0; eletype a,b; char c[80],str[15]={0},r; Initstack(&StackO); Push(&StackO,'='); Initstack(&StackN); gets(c); l=strlen(c); c[l]='='; l++; for(x=0;x=2){error();}} Push(&StackN,atof(str)); printf("%f",atof(str)); for(m=0;m<15;str[m]=0,m++); j=0; } else { if(!panduan(c[i])){error();} switch(Proceed(Gettop(&StackO),c[i])) { case '<': Push(&StackO,c[i]);i++;break; case '=': Pop(&StackO);i++;break; case '>': r=Pop(&StackO); if(sp->top==-1){error();} a=Pop(&StackN); if(sp->top==-1){error();} b=Pop(&StackN); Push(&StackN,Operate(a,r,b)); break; case ' ': error(); default : error(); } } } if(sp->top==-1){error();} printf("=%f",Gettop(&StackN)); return 0; } int main() { char ch; while(1) { printf("Mini Calc version 1.0 Copyright (c) 2011 Student\n>"); Evalexpres(&StackN); printf("\ninput 'q' to quit and 'enter' to start!"); do{ scanf("%c",&ch); if(ch=='q'||ch=='Q')return 0; }while(ch!='\n'); system("cls"); } }

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息