| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 5904 人关注过本帖
标题:逆波兰表达式求值
只看楼主 加入收藏
legendrlx
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2008-9-28
收藏
 问题点数:0 回复次数:16 
逆波兰表达式求值
一个用逆波兰法求包含非负实数表达式,并输出逆波兰表达式的程序

//////////////////////////////////////////////
///求包含非负实数的运算表达式的值////////////
///并输出逆波兰表达式///////////////////////
///////////////////////////////////////////
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<math.h>
#define STACK_INIT_SIZE 20//存储空间初始分配量
#define STACKINCREMENT  10//存储空间分配增量
typedef float SElemType;



typedef struct sqstack
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}*SqStack;



void InitStack(SqStack s)//构造栈
{
    s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!s->base)
    {
        printf("OVERFLOW!!");
        exit(1);
    }
    s->top=s->base;
    s->stacksize=STACK_INIT_SIZE;
}



void GetTop(SqStack s,SElemType *e)//读取栈顶元素
{
    if(s->top==s->base)
    {
        printf("The Stack Is Empty!!\n");
        exit(1);
    }
    *e=*(s->top-1);
}



void Push(SqStack s,SElemType e)//插入新元素
{
    if(s->top-s->base>=s->stacksize)
    {
        s->base=(SElemType *)realloc(s->base,(s-

>stacksize+STACKINCREMENT)*sizeof(SElemType));
                                                   //增大栈空间
        if(!s->base)
        {
            printf("The Stack Is Empty!!\n");
            exit(1);
        }
        s->top=s->base+s->stacksize;
        s->stacksize+=STACKINCREMENT;
    }
    *(s->top)=e;
    s->top++;
}



void Pop(SqStack s,SElemType *e)//删除栈顶元素
{
    if(s->top==s->base)
    {
        printf("The Stack Is Empty!!\n");
        exit(1);
    }
    *e=*(--s->top);
}



int In(char e)//判断是否为7种运算符之一
{
    switch(e)
    {
    case '+':
    case '-':
    case '*':
    case '/':
    case '(':
    case ')':
    case '#':return(1);break;//是运算符返回 1,否则,返回 0
    default:return(0);
    }
}



char Precede(char p,char c)//比较OPTR栈顶元素与取得元素的优先级
{                          //栈顶元素优先级高,返回 '>',反之返回 '<'
    switch(p)
    {
    case '+':
    case '-':
        switch(c)
        {
        case '*':
        case '/':
        case '(':return '<';break;
        default:return '>';break;
        }
        break;
    case '*':
    case '/':
        switch(c)
        {
        case '(':return '<';break;
        default:return '>';break;
        }
        break;
    case '(':
        switch(c)
        {
        case ')':return '=';break;
        case '#':printf("ERROR!!\n");exit(1);
        default:return '<';break;
        }
        break;
    case ')':
        switch(c)
        {
        case '(':printf("ERROR!!\n");exit(1);
        default:return '>';break;
        }
        break;
    case '#':
        switch(c)
        {
        case ')':printf("ERROR!!\n");exit(1);
        case '#':return '=';break;
        default:return '<';break;
        }
        break;
    }
}



SElemType Operate(SElemType x,char n,SElemType y)//四则运算
{
    SElemType e;
    switch(n)
    {
    case '+':e=x+y;break;
    case '-':e=x-y;break;
    case '*':e=x*y;break;
    case '/':
        if(y==0)//分母不能为 0
        {
            printf("The Denominator MUST NOT BE ZERO!!!\n");
            exit(1);
        }
        else
        {
            e=x/y;
            break;
        }
    }
    return e;
}



void main()
{
    SqStack OPTR,OPND;//定义运算符存储栈OPTR,数据存储栈OPND
    SElemType p,s,a,b,theta;
    char c,*str;//str存储逆波兰表达式
    int flag,decimal_place,strsize=STACK_INIT_SIZE,num=0,i=0;//flag记录运算

数是否为小数(是=1,否=0)
                                                             

//decimal_place记录运算数的小数位数
                                                             //strsize记录

str的大小
    OPTR=(SqStack)malloc(sizeof(SqStack));//分配空间
    OPND=(SqStack)malloc(sizeof(SqStack));
    str=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
    printf("Please Input The Expression Ending With '#'\n(Only including +

-*/ and non-negative Real Numbers):\n");
    InitStack(OPTR);//创建运算符存储栈
    Push(OPTR,'#');
    InitStack(OPND);//创建数据存储栈
    c=getchar();
    GetTop(OPTR,&p);//p为栈顶元素
    while(c!='#'||p!='#')
    {
        if(!In(c))//不是运算符,存入数据栈
        {
            if(num>=strsize)//为str增加空间
            {
                str=(char *)realloc(str,

(strsize+STACKINCREMENT)*sizeof(char));
                strsize=strsize+STACKINCREMENT;
            }
            str[num++]=c;
            flag=0;
            decimal_place=0;
            s=c-48;//字符与数字转换
            c=getchar();
            while(c>='0'&&c<='9'||c=='.')
            {
                if(num>=strsize)
                {
                    str=(char *)realloc(str,

(strsize+STACKINCREMENT)*sizeof(char));
                    strsize=strsize+STACKINCREMENT;
                }
                str[num++]=c;
                if(c=='.')
                {
                    flag=1;
                    c=getchar();
                    continue;
                }
                if(flag==1)decimal_place++;
                s=s*10+(c-48);
                c=getchar();
            }
            if(num>=strsize)
            {
                str=(char *)realloc(str,

(strsize+STACKINCREMENT)*sizeof(char));
                strsize=strsize+STACKINCREMENT;
            }
            str[num++]='#';
            s=s/pow(10,decimal_place);
            Push(OPND,s);
        }
        else
        {
            switch(Precede(p,c))
            {
            case '<':Push(OPTR,c);//栈顶元素优先级低,将c存入栈
                c=getchar();break;
            case '=':Pop(OPTR,&s);//两者优先级相同,脱去括号
                c=getchar();break;
            case '>':Pop(OPTR,&theta);//栈顶元素优先级高,取出OPTR中

运算符theta,取出OPND中两数据a,b,用c运算,将结果存入OPND
                Pop(OPND,&b);Pop(OPND,&a);
                Push(OPND,Operate(a,theta,b));
                if(num>=strsize)
                {
                    str=(char *)realloc(str,

(strsize+STACKINCREMENT)*sizeof(char));
                    strsize=strsize+STACKINCREMENT;
                }
                str[num++]=theta;
                str[num++]='#';
                break;
            }
            GetTop(OPTR,&p);
        }        
    }//while
    printf("\n");
    printf("The Reverse Polish Notation is:\n");
    while(i<num)//输出逆波兰表达式
    {
        if(str[i]=='#')printf(" ");
        else printf("%c",str[i]);
        i++;
    }
    printf("\n\n");
    GetTop(OPND,&p);
    printf("Answer is:%f\n",p);
}



欢迎大家指正!!
搜索更多相关主题的帖子: 波兰 求值 表达 
2008-10-18 21:53
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
是中缀转后缀再计算吗?不错不错,应该是用了icp和isp吧?
2008-10-18 22:38
legendrlx
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2008-9-28
收藏
得分:0 
回复 2# geninsf009 的帖子
一边计算值,一边转为后缀表达式。弱问一下,什么是icp和isp??请多指教呀!!
2008-10-18 23:36
legendrlx
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2008-9-28
收藏
得分:0 
一楼的程序复制到VC++6.0中会由于换行而不能运行,可以下载下面附件进行运行。

逆波兰表达式求值.pdf (46.35 KB)
2008-10-18 23:44
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
icp是栈外优先级,isp是栈内优先级,
我写的程序先转后缀表达式,再根据后缀表达来求解的,
程序写的很冗长,就不贴上来了,估计没你的算法先进...
2008-10-20 10:40
legendrlx
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2008-9-28
收藏
得分:0 
谢谢楼上!!你可以用附件传上来呀!!
2008-10-20 16:00
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
打开dsw文件直接运行就可以了,里面用了一个链式的堆栈,一起写的代码一共加起来过1000行了,所以冗长...

Caculator.rar (668.4 KB) 表达式计算器完整程序

2008-10-20 18:41
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
我写的程序中,不支持表达式的换行,程序中真正用在表达式计算上的代码并不多,

更多的代码耗费在怎样把一个表达式字符串中的数字,符号,小数点等全部识别出来,

并提取出来进行相应的计算处理...

ps:特别是带小数点的数从表达式字符串中提取出来,有点繁琐...

[[it] 本帖最后由 geninsf009 于 2008-10-20 18:56 编辑 [/it]]
2008-10-20 18:44
welove1012
Rank: 1
等 级:新手上路
帖 子:29
专家分:0
注 册:2008-10-15
收藏
得分:0 
好!!
交流的好!!
顶!!
受益啊!
2008-10-24 12:29
guohuangbo
Rank: 1
等 级:新手上路
帖 子:19
专家分:0
注 册:2008-9-3
收藏
得分:0 
楼上!!你可以用附件传上来呀!!
2008-10-26 13:59
快速回复:逆波兰表达式求值
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019517 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved