/*
Name:infixSuffixConv.c
Copyright: personal
Author: hojor
Date: 10-06-10 21:24
Description: infix convert to suffix
*/
#include<stdio.h>
#include<stdlib.h>
#define STACK_SIZE 20
////~stack start
//stack struct
typedef struct stack{
int top;
int a[STACK_SIZE];
}stack;
//create stack
stack * createStack()
{
stack * s = (stack *)malloc(sizeof(stack));
s->top = -1;
return s;
}
//get the the top value of stack
int getTop(stack * s)
{
return s->a[s->top];
}
//is stack empty?
int isEmpty(stack * s)
{
return s->top == -1;
}
//is stack full?
int isFull(stack * s)
{
return s->top == (STACK_SIZE-1);
}
//pop stack return value
int pop(stack * s)
{
if(!isEmpty(s))
{
return s->a[s->top--];
}
else
{
printf("stack empty!!\n");
return 0;
}
}
//push value x to stack
void push(stack * s,int x)
{
if(!isFull(s))
{
s->a[++s->top] = x;
}
else
{
printf("stack is full!!\n");
}
}
////~
////~infix suffix convert start
//get the level of symbol
int getLevel(char symbol)
{
switch(symbol)
{
case '(':
return 10;
break;
case '*':
case '/':
return 9;
break;
case '+':
case '-':
return 8;
break;
default:
printf("symbol error!!:[%c]\n",symbol);
}
}
//is char symbol??
int isSymbol(char ch)
{
return (ch == '(')||(ch == '*')||(ch == '/') \
||(ch == '-')||(ch == '+')||(ch == ')');
}
//function of convert infix to suffix
void infix_suffix_convert(char * infixStr,char * suffixStr)
{
stack * symStack = createStack();
int iCount = strlen(infixStr),i,flag,j,k,n;
i=j=k=flag=n=0;
for(i=0;i<=iCount;i++)
{
//表达式中读到字符为运算符
if(isSymbol(infixStr[i]))
{
/*符号入栈条件,如果当前读取的符号不是闭合括号,并且栈为空或栈顶
为开括号或栈顶的符号优先级小于当前读取符号则符号入栈*/
if(( isEmpty(symStack) && \
infixStr[i] != ')' )
|| ( (char)getTop(symStack)=='(' && \
infixStr[i] != ')' )
|| ( infixStr[i]!=')' && \
getLevel((char)getTop(symStack)) < getLevel(infixStr[i]) ))
{
push(symStack,infixStr[i]);
}
else if(infixStr[i] == ')')
{/*如果遇到闭合括号,符号出栈,输出,直到开括号出栈为止*/
while((char)getTop(symStack)!='(')
{
sprintf(suffixStr,"%s %c",suffixStr,pop(symStack));
}
pop(symStack);
}
else
{/*如果栈为非空并且栈顶符号优先级大于当前读取的符号则出栈,
输出,直到栈顶符号的优先级小于当前读取的符号为止*/
while(!isEmpty(symStack) &&
(getLevel((char)getTop(symStack)) \
>= getLevel(infixStr[i])) )
{
sprintf(suffixStr,"%s %c",suffixStr,pop(symStack));
}
push(symStack,infixStr[i]);
}
flag=2;
}
else if(infixStr[i]>='0' && infixStr[i]<='9')
{//表达式中读取的字符为数字,输出
if(flag == 2 || flag == 0)
{
sprintf(suffixStr,"%s %d",suffixStr,atoi(&infixStr[i]));
flag = 3;
}
}
else
{
;
}
}
//因数字已经全部输出,故栈内所有符号出栈,输出
while(!isEmpty(symStack))
sprintf(suffixStr,"%s %c",suffixStr,pop(symStack));
}
////~
int main()
{
///---stack test
printf("\n********** stack test ***********\n");
int i,j=0,k=0;
stack * s = createStack();
for(i=0;i<10;i++)
push(s,i);
for(i=0;i<10;i++)
printf("%d ",pop(s));
putchar('\n');
free(s);
///---convert start
printf("\n********* convert start **********\n");
int a = 50;
char * infix="( 177 + 25 ) * 555 + (35 + 655 )";
printf("\n中缀表达式:\n%s\n",infix);
char suffix[100];
memset(suffix,0,sizeof(suffix));
infix_suffix_convert(infix,suffix);
printf("\n后缀表达式:\n%s\n\n",suffix);
system("pause");
return 0;
}
分享到:
相关推荐
利用C语言实现中缀表达式转化为后缀表达式!!利用栈。
c语言实现中缀表达式转后缀表达式并求得计算结果,用顺序栈结构。 当输入者输入错误信息的时候需要报错,并说明错误的种类。
一个简单的算法,利用栈实现中缀表达式与后缀表达式的转换
数据结构的中缀表达式转后缀表达式,通过C++语言实现。使用堆栈方法进行转换,能正确运算包含括号、加、减、乘、除复合运算,如(1+2)*3-1.8*(18/(7+2)) = 8.2。
编译系统对中缀表达式的处理方法是先把它转换为后后缀表达式.在后缀表达式中,运算符位于两个操作数的后面,并且没有括号,其运算符的次序就是其执行运算的次序。后缀表达式计算过程的规则非常简单:从左到右依次扫描,...
栈实现中缀表达式到后缀表达式的转换 InfixToSuffix 用C语言编写 code blocks开发
用栈实现中缀表达式转为后缀表达式,规定了各个符号的优先级,可以说是对栈概念的深入理解
/*程序由本人编译,并且经过多次测试,正确无误!目前该转换算法只支持数字在0至9之间的+-*/四元运算转换.*/ /**************程序员信息 ***************东北大学*******************东大很厉害**************** ...
c++使用堆栈实现中缀表达式转后缀表达式
c语言实现中缀表达式向后缀表达式转换 分类:算法+数据结构
用户输入中缀表达式,程序输出后缀表达式并输出计算结果
用二叉树实现中缀表达式转换成后缀表达式,内含一个CPP文件的代码和一个截图,很不错的,是我自己写的。
问题描述 中缀表达式就是我们通常所书写的数学...要求:使用栈数据结构实现 ,输入的中缀表达式以#号结束 输入 整数N。表示下面有N个中缀表达式 N个由单个字母和运算符构成的表达式 输出 N个后缀表达式。
中缀表达式转后缀表达式,并进行计算; 支持: 支持函数: Abs 绝对值 Power 幂 Sqr 平方 Sqrt 平方根 Abs Sqr Sqrt 需要加括号 Power不需要 * 后缀运算符: * 第1级: () 从左到右 * 算出运算符: * 第4级:* \ % 从...
08.中缀表达式转换后缀表达式算法.ppt
中缀表达式转后缀生产表达式二叉树,并在控制台中画出。
自定义栈,中缀表达式转换为后缀表达式并求值,三个抽象数据类型定义(1.class stack 2.class Middle_expressionToPost_expression 3.class Post_expression_value)