怎样用一个队列和一个栈实现求一个表达式的值？大致功能已实现，细节弄不懂！ - 编程论坛

大致功能已实现，就是在入队的值和出队的时候弄不清楚，导致求出的值不对。

求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);

}