算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
输入格式:
输入在一行中给出不含空格的中缀表达式,可包含+
、-
、*
、/
以及左右括号()
,表达式不超过20个字符。
输出格式:
在一行中输出转换后的后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。
输入样例:
2+3*(7-4)+8/4
输出样例:
2 3 7 4 - * + 8 4 / +
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define MAXL 21
typedef enum{
false,true
} bool;
typedef char ElementType;
//堆栈定义
typedef int Position;
typedef struct SNode *PtrToSNode;
struct SNode{
ElementType *Data;
Position Top;
int MaxSize;
};
typedef PtrToSNode Stack;
Stack createStack(int MaxSize);
bool isEmpty(Stack s);
void push(Stack s,ElementType X);
ElementType pop(Stack s);
ElementType peek(Stack s);
typedef enum{
lpr,rpr,plus,minus,times,divide,eos,operand
} Precedence;//运算符的优先级类型
bool isSign(char *expr,int i);
char getOp(char *expr,int *i,char *postfix,int *j);
Precedence getToken(char op);
void toPostfix(char *expr);
int main()
{
char str[MAXL];
scanf("%s",str);
toPostfix(str);
return 0;
}
void toPostfix(char *expr)
{
int i,j,l;
char postfix[2*MAXL],op;
Stack s;
Precedence token;
j=0;
s=createStack(MAXL);
l=strlen(expr);
//j=0;//j指向postfix[]中当前要写入的位置
for(i=0;i<l;i++){
op=getOp(expr,&i,postfix,&j);
token=getToken(op);
if(token==operand)
continue;//不处理数字
switch(token){
case lpr : push(s,'(');break;//左符号入栈
case rpr ://括号内中缀表达式扫描完毕
//把左括号前的所有运算符写入postfix[]
while(peek(s)!='('){
postfix[j++]=pop(s);
postfix[j++]=' ';
}
pop(s);//删除左括号
break;
default ://其他运算符
while(!isEmpty(s) && peek(s)!='(' && token<=getToken(peek(s))){
postfix[j++]=pop(s);
postfix[j++]=' ';
}
push(s,op);
break;
}
}
while(!isEmpty(s)){
postfix[j++]=pop(s);
postfix[j++]=' ';
}
postfix[j-1]='\0';
printf("%s\n",postfix);
}
//堆栈实现
Stack createStack(int MaxSize)
{
Stack s=(Stack)malloc(sizeof(struct SNode));
s->Data=(ElementType *)malloc(MaxSize*sizeof(ElementType));
s->Top=-1;
s->MaxSize=MaxSize;
return s;
}
bool isEmpty(Stack s)
{
return (s->Top==-1);
}
void push(Stack s,ElementType x)
{
//简版入栈,不担心栈满的情况
s->Data[++(s->Top)]=x;
}
ElementType pop(Stack s)
{
//简版出栈,不担心栈空
return (s->Data[(s->Top)--]);
}
ElementType peek(Stack s)
{
return s->Data[s->Top];
}
//判断出现'-'为负数,不是运算符减号
bool isSign(char *expr,int i)
{
if(!i || ((!isdigit(expr[i-1]) && (expr[i-1]!=')'))))
return true;
else
return false;
}
char getOp(char *expr,int *i,char *postfix,int *j)
{
//如果是数字则直接写入postfix[]并返回'0'
//如果是运算符则返回字符
if(isdigit(expr[(*i)])) {
while(isdigit(expr[(*i)]) || (expr[(*i)]=='.'))
postfix[(*j)++]=expr[(*i)++];
postfix[(*j)++]=' ';
(*i)--;
return '0';
}
switch(expr[(*i)]){
case '+':
if(isSign(expr,(*i))){//如果是正号
(*i)++;
return getOp(expr,i,postfix,j) ;
}else
return '+';
case '-':
if(isSign(expr,(*i))){//如果是负号
postfix[(*j)++]='-' ;
(*i)++;
return getOp(expr,i,postfix,j) ;
}else
return '-';
default:
return expr[(*i)];
}
}
Precedence getToken(char op)
{
//返回运算符优先级
switch(op){
case '(':return lpr;
case ')':return rpr;
case '+':return plus;
case '-':return minus;
case '*':return times;
case '/':return divide;
case '\0':return eos;
default : return operand;
}
}
标签:return,int,3.11,char,expr,习题,ElementType,Stack,表达式 From: https://blog.csdn.net/qq_33811080/article/details/140472460