| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1932 人关注过本帖
标题:怎样用一个队列和一个栈实现求一个表达式的值?大致功能已实现,细节弄不懂 ...
只看楼主 加入收藏
未遂1002
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2018-11-28
结帖率:100%
收藏
 问题点数:0 回复次数:1 
怎样用一个队列和一个栈实现求一个表达式的值?大致功能已实现,细节弄不懂!
大致功能已实现,就是在入队的值和出队的时候弄不清楚,导致求出的值不对。

求3*(6-2)这个表达式。
题目如下
将中缀表达式转化成后缀表达式存储在队列中,然后利用后缀表达式求表达式的值并输出。
将中缀表达式转化成后缀的思想:
1、创建一空队列,用来存放后缀表达式,建立并初始化操作符栈OPTR,将表达式起始符“#”压入OPTR栈。
2、依次读入表达式中每个字符ch,循环执行(3)至(5),直至求出整个表达式转换完毕。
3、取出OPTR的栈顶元素,当OPTR的栈顶元素和当前读入的字符ch均为“#”时,整个中缀表达式转换完毕。
4、若ch不是运算符,则进队,读入下一字符ch。
5、若ch是运算符,则根据OPTR的栈顶元素和ch的优先权比较结果,做不同的处理。
① 若是小于,则ch压入OPTR栈,读入下一字符ch。
② 若是大于,则弹出OPTR栈顶的运算符,进队。
③ 若是等于,则OPTR的栈顶元素是“(”且ch是“)”,这时弹出OPTR栈顶的“(”,相当于去掉括号,然后读入下一字符ch。


程序代码:
#include<stdio.h> 
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#define OVERFLOW -2
#define MAXSIZE 100
#define OK 1 
#define ERROR 0
#define TRUE 1
#define FALSE 0
#include<iostream>
using namespace std;

typedef int Status;
typedef char SElemType;


typedef struct
{
    SElemType *base;
    int front;
    int rear;
}SqQueue;

Status InitQueue(SqQueue &Q)  //初始化
{

    Q.base=new SElemType[MAXSIZE];
    if(!Q.base) exit(OVERFLOW);
    Q.front=Q.rear=0;
    return OK;
}
Status EnQueue (SqQueue &Q,SElemType e)  //入队
{
    if((Q.rear+1)%MAXSIZE==Q.front)
        return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXSIZE;
    return OK;

}
Status DeQueue(SqQueue &Q,SElemType &e)  //出队
{
    if(Q.front==Q.rear)
        return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXSIZE;
    return OK;
}
SElemType GetHead(SqQueue Q)//取队头元素
{
    if(Q.front!=Q.rear)
        return Q.base[Q.front];
}


//--------顺序栈的存储结构------
typedef struct 
{
    SElemType *base;    //栈底指针 
    SElemType *top;    //栈顶指针 
    int stacksize;     //占可用的最大容量 
}SqStack; 


Status InitStack (SqStack &S)
{//构造一个空栈 
    S.base=new SElemType[MAXSIZE];   //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间 
    if (!S.base) exit(OVERFLOW);    //动态分配失败
    S.top=S.base;     //top初始为base,空栈 
    S.stacksize=MAXSIZE;   //stacksize置为栈的最大容量MAXSIZE 
    return OK;
    
}

Status Push(SqStack &S,SElemType e) 
{//插入元素e为新的栈顶元素
    if(S.top-S.base==S.stacksize)   return ERROR;   //栈满 
    *S.top++=e;    //元素e压入栈顶,栈顶指针加1 
    return OK;
    
}

Status Pop(SqStack &S,SElemType &e)
{//删除s的栈顶元素,用e返回其    
    if (S.top==S.base)  return ERROR;  //栈顶 
    e=*--S.top;   // 栈顶指针减1,将栈顶元素为e 
    return OK;
    
} 

SElemType GetTop(SqStack S) 
{//返回S的栈顶元素,不修改栈顶指针、
    if(S.top!=S.base)   //栈非空
        return *(S.top-1);   //返回栈顶元素的值,栈顶指针不变     
}


Status In(SElemType c)
{
    switch(c)          //判断读入的字符是哪一种运算符, 
    {
        case '+':
            return TRUE;
            break; 
        case '-':
            return TRUE;
            break;
        case '*':
            return TRUE;
            break;
        case '/':
            return TRUE;
            break;
        case '(':
            return TRUE;
            break;
        case ')':
            return TRUE;
            break;
        case '#':
            return TRUE;
            break;
        default:
            return FALSE;
            
    }
}

SElemType Precede(SElemType t1,SElemType t2)
{
    SElemType f;       
    switch(t2)     //判断运算符栈的栈顶元素和读入的运算符之间谁的优先级更高,并返回结果 
    {
        case '+':
            if (t1=='('||t1=='#')
                f='<';
            else
                f='>';
            break;
            
        case '-':
            if (t1=='('||t1=='#')
                f='<';
            else
                f='>';
            break;
            
        case '*':
            if (t1=='+'||t1=='-'||t1=='('||t1=='#')
                f='<';
            else
                f='>';
            break;
            
        case '/':
            if (t1=='+'||t1=='-'||t1=='('||t1=='#')
                f='<';
            else
                f='>';
            break;
                
        case '(':
            if (t1=='+'||t1=='-'||t1=='('||t1=='#'||t1=='*'||t1=='/')
                f='<';
            break;
            
        case ')':
            if (t1=='+'||t1=='-'||t1=='*'||t1=='/'||t1==')')
                f='>';
            else if (t1=='(')
                f='=';
            break;
            
        case '#':
            if (t1=='#')
                f='=';
            else
                f='>';
            break;    
        default:
            cout<<"输入超出范围。。。";
        
    }
    return f;
}


SElemType Operate(SElemType a,SElemType theta,SElemType b)
{    
    SElemType c;
    a=a-'0';      //因为a,b均为字符型,所以转化成int型 
    b=b-'0';
    switch(theta)
    {
        case '+':
            c=a+b+'0';break;        //再将计算的结果转化为字符型 
        case '-':
            c=a-b+'0';break;
        case '*':
            c=a*b+'0';break;
        case '/':
            c=a/b+'0';break;        
    }
    return c;   //返回计算结果 
}

char EvaluateExpression()
{//算数表达式求值的算符优先算法,设OPTR和 OPND分别为运算符栈和操作数栈
    SqStack OPTR;
    SqQueue OPND;
    char ch,theta,a,b,c,x,w;
    InitQueue(OPND);  //初始化OPND队列
    InitStack(OPTR);  //初始化OPTR栈 
    Push(OPTR,'#');   //将表达式起始符“#”OPTR栈 
    cin>>ch;
    while (ch!='#'||GetTop(OPTR)!='#')    //表达式没有扫描完毕或者OPTR的栈顶元素不为“#” 
    {
        if (!In(ch))     //判断ch是不是运算符,不是则入OPND队 
            {
                EnQueue(OPND,ch);
             cin>>ch;
            }
        else
            switch(Precede(GetTop(OPTR),ch))   // 比较OPTR的栈顶元素和ch的优先级 
            {
                case '<':
                    Push(OPTR,ch);        //当前字符ch压入OPTR栈 ,读入下一个字符ch 
                    cin>>ch;
                    break;
                case '>':
                    Pop(OPTR,theta);    //弹出OPTR栈顶的运算符 
                    b=GetHead(OPND);        //弹出OPND队列的运算数, 
                    a=GetHead(OPND);        //弹出OPND队列的运算数,
                    EnQueue(OPND,Operate(a,theta,b));   //将运算结果入OPND队列 
                    break;
                case '=':               //OPTR的栈顶元素是“(”且ch是“)”
                    Pop(OPTR,x);        //弹出OPTR栈顶的"(",
                    cin>>ch;            //读入下一个字符ch 
                    break;
                
            }
    }
    return GetHead(OPND);              //OPND队列元素即为表达式求值结果 
    
}
int main()
{
    char w;
    cout<<"请输入算数表达式,并以#结束\n";
    w=EvaluateExpression();    //将运算结果赋值给w 
    w=w-48;         //将字符转换成数字 
    printf("The result of expression is %d\n",w); 
                   
}


搜索更多相关主题的帖子: return case  || break 
2019-10-19 21:15
cp19045
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2019-10-22
收藏
得分:0 
谢谢
2019-10-22 23:41
快速回复:怎样用一个队列和一个栈实现求一个表达式的值?大致功能已实现,细节弄 ...
数据加载中...
 
   



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

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