表达式求值算法

表达式求值，一般采用栈和队列的方式来求值，下面介绍表达式求值的两种算法。

方法一、使用两个栈，一个为操作符栈OPTR(operator)，一个是操作数栈OPND(operand)
算法过程：
当输入 3 * ( 4 - 1 * 2 ) + 6 / ( 1 + 1 )时，为简单方便，我们输入时，按照字符的顺序一个一个的处理，比如

ch = getchar()

然后根据ch 的值判断。

• 若 ch 是数字，直接压入操作数栈OPND；
  
• 若 ch 是'('，直接入栈OPTR;若 ch 是')'，若OPTR 和 OPND 非空，弹出OPTR的栈顶操作符，弹出OPND栈顶的两个操作数，做运算，然后见个结果压入栈OPND，直到弹出的OPTR栈顶元素时')';
• 若 ch 是操作符(比如+, -, *, /)，如果OPTR栈顶元素是 (，直接入栈OPTR，如果不是'('且OPTR栈非空且栈顶元素操作符的优先级大于ch，那么弹出OPTR的栈顶操作符，并弹出OPND中栈顶的两个元素，做运算，将运算结果入栈OPND，此时，重复这一步操作；否则将ch入栈OPTR；
• 若ch为EOF，说明表达式已经输入完成，判断OPTR是否为空，若非空，一次弹出OPTR栈顶操作符，并与OPND栈顶两个元素做运算，将运算结果入栈OPND，最后表达式的结果即OPND的栈底元素。

以表达式3 * ( 4 - 1 * 2 ) + 6 / ( 1 + 1 )为例，计算过程如下所示：

通过上述的计算过程，写出伪代码如下所示：

void GetExpress(Stack * OPTR, Stack * OPND)
{
    char ch;
    while ((ch = getchar ()) != EOF) {
        if (IsDigit (ch)) {
            PushStack (OPND, ch);
        }
        else if (ch == '(')
            PushStack (OPTR, ch);
        else if (ch == ')') {
            while (!IsStackEmpty(OPTR)) {
                PopStack (OPTR, op);
                if (op == ')')
                    break;
                PopStack (OPND, num2);
                PopStack (OPND, num1);
                res = Calc (num1, num2, op);
                PushStack (OPND, res);
            }
        }
        else if (ch == '+' || ch == '-'
            || ch == '*' || ch == '/') {
            while (!IsStackEmpty (OPTR) && GetTop (OPTR)!='(' && GetTop (OPTR)>ch) {
                PopStack (OPTR, op);
                PopStack (OPND, num2);
                PopStack (OPND, num1);
                res = Calc (num1, num2, op);
                PushStack (OPND, res);
            }
            if (IsStackEmpty (OPTR) || GetTop(OPTR)=='(')
                PushStack (OPTR, ch);
        }
    }
}
// 当表达式输入完成后，需要对OPTR栈和OPND中的元素进行运算
int GetValue(Stack * OPTR, Stack * OPND)
{
    while (!IsStackEmpty (OPTR)) {
        PopStack (OPTR, op);
        PopStack (OPND, num2);
        PopStack (OPND, num1);
        res = Calc (num1, num2, op);
        PushStack (OPND, res);
    }
    // 最后的操作数栈OPND栈顶元素即是表达式的值
    return GetTop(OPND);
}

PS: 上面没有指出表达式非法的情况

方法二：采用中缀表达式的方法，求取表达式的中缀表达式，借用一个操作符栈OPTR和中缀表达式队列Queue，求取中缀表达式，然后对中缀表达式求值。

求取中缀表达式

• 若 ch 是数字，直接入队列Queue;
• 若 ch 是操作符(+, -, *, /)，如果OPTR栈顶元素是(或者OPTR 为空，直接入栈OPTR;若OPTR非空，且栈顶元素的优先级大于ch，先出栈，且将出栈元素入队Queue，直到栈顶元素小于ch，然后将ch入栈；否则直接将ch入栈；
• 若 ch 是 (，直接入栈 OPTR;
• 若 ch 是 )，出栈并入队列，直到出栈元素是 (，若栈为空且没有(出现，说明表达式非法。
• 当表达式输入完成时，判断栈是否为空，若非空，依次弹栈并入队列

求取中缀表达式的值，需要借用一个栈

• 若队列非空，出队q_ele；如果出队元素q_ele是数字，入栈S；否则取出栈顶两个元素，与q_ele这个操作符左运算，运算结果入栈S
• 最后的结果为栈顶元素

仍以表达式3 * ( 4 - 1 * 2 ) + 6 / ( 1 + 1 )为例，计算过程如下：

计算中缀表达式：

此时中缀表达式为3,4,1,2,*,-,*,6,1,1,+,/,+，队列左边是头，右边是尾。

计算中缀表达式的值：

根据以上操作过程，写出伪代码：

void GetPostExpress (Stack * OPTR, Queue * Q)
{
    while ((ch = getchar ()) != EOF) {
        if (IsDigit (ch))   //判断是否是数字
            PushQueue (Q, ch);
        else if (ch == '(')
            PushStack (OPTR, ch);
        else if (ch == '+' || ch == '-'
            || ch == '*' || ch == '/') {
            if (IsStackEmpty (OPTR) || GetTop (OPTR)=='(')
                PushStack (OPTR, ch);

            while (!IsStackEmpty (OPTR) && GetTop (OPTR)!='('
                && GetTop (OPTR)>ch) {
                PopStack (OPTR, op);
                PushQueue (Q, op);
            }
            PushStack (OPTR, ch);
        }

        if (ch == ')') {
            while (!IsStackEmpty (OPTR)) {
                PopStack (OPTR, op);
                if (op == ')')
                    break;

                PushQueue (Q, op);
            }
        }
    }
    // 表达式输入完成 
    while (!IsStackEmpty (OPTR)) {
        PopStack (OPTR, op);
        PushQueue (Q, op);
    }
}

// 计算中缀表达式的值
int GetValue (Queue * Q, Stack * S)
{
    while (!IsQueueEmpty (Q)) {
        PopQueue (Q, ch);
        if (IsDigit (ch))
            PushStack (S, ch);
        else {
            PopStack (S, num2); //需要判断栈是否为空
            PopStack (S, num1);
            res = Calc (num1, num2, ch);
            PushStack (S, res);
        }
    }
    return GetTop (S);  //栈顶元素就是表达式的结果
}