Yan`s Notepad

--- My Notepad......Articles, tools and etc.
栈和计算算术表达式的值
栈是一种数据结构,遵循后进先出的原则。它只允许在一个表的某一端进行插入和删除的操作,其中,插入的操作叫做入栈(push),删除的操作叫做出栈(pop)。用图来表示就是这样的:
small
上图的top指向栈顶,叫做栈顶指针,在上图中,栈顶指针(地址)是一值增加的,我们把栈顶指针的这种增长方式叫做向上增长,反过来说,栈顶指针一直减少的增长方式叫做向下增长。在下面的内容中,栈的实现都是使用数组实现的,并且是向上增长的,怎么实现本身对下面的内容没有影响。当然,你也可以使用链表实现一个栈,或是一个向下增长的栈。使用数组来实现栈的话,可以很方便的实现栈顶指针——把它作为数组下标就可以了。因此,我们需要储存一个栈顶指针top,对应存放栈数据的数组dat,写成代码就是:
typedef struct _SEQSTACK
{
    		char        dat[STACK_DEEP];
    		int	        top;                    	// 栈顶指针
}SEQSTACK;
其中,char是栈的数据类型。按照需要更改。以该数据结构为例子,那么我们即可给出入栈、出栈等的操作。规定,以栈顶指针top为0表示栈是空的,栈顶指针top指向的数组下标永远是栈顶元素的下一个位置。假如不考虑栈是否已经空了的话,那么栈的相关操作可以用简单的宏定义完成:
#define  STACK_INIT(stk)             stk.top = 0 
#define  STACK_PUSH(stk, d)          stk.dat[stk.top++] = d
#define  STACK_POP(stk)              stk.dat[--stk.top]
至此,得到了出入栈的操作。注意,该操作和第一张图所不同的地方在于:第一张图的top指向栈顶元素,而该操作的top则是指向栈顶元素的下一个位置。这不会带来影响,但是在取栈顶元素的时候要将top减去1,也就是:
#define  STACK_TOP(stk)              stk.dat[stk.top - 1]
同样的,因为规定了top为0是空栈,因此可以得到判断栈是否为空的宏:
#define  STACK_EMPTY(stk)            (stk.top == 0)
注意一点,栈操作过程中是可能溢出的,我们这里的操作函数没有判断,意味着实际使用中需要判断。栈溢出,也就是超过了栈的允许大小、栈中只有一个元素却要求弹出两次等。
至此,栈的操作就结束了。下面的图片、描述中,所使用的栈均基于我们现在提到的栈,操作使用我们现在所给的这几个宏定义。
下面来看栈的一个经典应用:算术表达式求值。
这个问题的描述很简单:给定一个算术表达式,例如3-2*5或者是5-2*(-1+2.1)这样的式子,要求程序给出结果。乍看该问题很难,但是我们可以借助逆波兰表达式(后缀表达式)来完成这个事情。
在明白逆波兰表达式是什么之前,先需要知晓运算符优先级。简而言之,高运算符优先级的运算符先执行,然后是低的。按照先加减后乘除的规则,我们容易知道加减号的优先级大于乘除号的优先级。同样的,负号的优先级小于乘除号的优先级。因此,针对于运算符优先级,我们可以给出下面的顺序:加减>乘除>负号。
逆波兰表达式,又叫后缀表达式。顾名思义,它是一种运算符全部都在末尾的表达式,整个表达式不含括号,由波兰逻辑学家J.Lukasiewicz于1929年提出。我们平时使用的表达式,比如5-2*(-1+2.1),叫做中缀表达式——运算符在操作数中间。同样的,把运算符全部扔到操作数前面叫做前缀表达式,整个表达式不含括号,不过关于前缀表达式的具体内容不再提及。现在,你应该明白为什么使用逆波兰表达式了——它没有括号,只剩下运算符。这使得我们可以专心于运算符的处理。自然地,也可以使用前缀表达式完成相应的任务。不过既然是说了用逆波兰表达式,还是专心于逆波兰表达式吧。
首先,我们需要把一个中缀表达式转换为一个逆波兰表达式。它的具体步骤为:
1. 遍历中缀表达式的每一个字符,得到字符p。
2. 如果字符p是左括号‘(’,就往栈stack中入栈该括号。
3. 如果字符p是右括号‘)’,就弹出栈中的所有运算符到逆波兰表达式输出,直到遇到左括号,并弹出左括号。
4. 如果字符p是运算符,则弹出低于或者等于当前优先级的运算符到逆波兰表达式输出,直到栈为空或者遇到左括号。
5. 如果字符p是数字,则将数字送入逆波兰表达式输出。
6. 回到步骤1,遍历完整个表达式。
7. 弹出栈中剩余的运算符到逆波兰表达式输出。
比如表达式5-2*(1+2),按照上述步骤,转换就是这样:
small
不过这里提一个技巧,当你需要人工计算逆波兰表达式的时候,可以使用这样的方式计算:给所有的运算式子外面加上括号,把所有的运算符提出到上一级括号的后面,然后再去掉括号,也可以得到逆波兰表达式:5 - 2 * (1 + 2) => (5 - (2 * (1 + 2))) => (5 - ( 2 * (1 2)+)) ...=>(5 (2 (1 2)+)*)- => 5 2 1 2 +*-,是一样的结果。这个小技巧说不定可以在某年某月的考试中助你一臂之力,因而提一下。
转换的原理便是如此,现在我们来考虑实现:很明显,我们需要一个运算符优先级判断的函数。这个函数很好实现,只需要判断输入的字符,然后返回数字表示运算符优先级即可,比如:
int GetCalaLevel(char c)
{
    if (c == CALC_Neg)
        return 1;
    else if (c == '*' || c == '/')
        return 2;
    else if (c == '+' || c == '-')
        return 3;
    return 0;
}
然后再来考虑转换的问题。按照上面的思路,写出一个转换程序应该是不难的了。但是注意,我们应该考虑一下负号——当减号‘-’前面不是操作数的时候,减号就是负号了。考虑特殊情况——减号最开始的位置,前面是无法被取到的,因为数组会越界。但是这个时候减号也是负号。为了判断,定义下面的宏。同时为了分开各个操作数,我们也用空格划开它们,我们使用最开始定义的宏和SEQSTACK那个栈的结构体,可以完成下面的代码:
#define  CALC_Neg                    '!'                // 机器认的负号, 不是我们输入的负号
#define  COMPILE_CUT                 ' '                // 分隔符, 分开操作数
#define  IS_NUMBER(a)                (((a) >= '0' && (a) <= '9') || (a) == '.')
void buildPoland(const char *mid, char *end)
{
    const char *p;
    char        dat;
    SEQSTACK    stack;
    STACK_INIT(stack);
    p = mid;
    while (*p)
    {
        if (*p == '(')
        {
            STACK_PUSH(stack, *p);
        }
        else if (*p == ')')
        {
            while (!STACK_EMPTY(stack) && STACK_TOP(stack) != '(')
            {
                dat = STACK_POP(stack);
                *(end++) = dat;
            }
            STACK_POP(stack);                   // 弹掉'('
        }
        else if (IS_NUMBER(*p))
        {
            do {                                // 载入连续的数字
                *(end++) = *(p++);
            } while (IS_NUMBER(*p));
            *(end++) = COMPILE_CUT;             // 分段开
            p--;
        }
        else {                                  // 运算符
            int lev;
            dat = *p;
            if (*p == '-' && ((p - mid > 1 && !IS_NUMBER(*(p - 1))) || p - mid == 0))
                dat = CALC_Neg;                 // -前面不是操作数, 那么说是负号
            lev = GetCalaLevel(dat);            // 当前运算符优先级
            while (!STACK_EMPTY(stack) && GetCalaLevel(STACK_TOP(stack)) <= lev && STACK_TOP(stack) != '(')
            {
                *(end++) = STACK_POP(stack);    // 连续弹出低于或者等于当前优先级的运算符
            }
            STACK_PUSH(stack, dat);             // 入栈当前运算符
        }
        p++;
    }
    while (stack.top != 0)				        // 把剩下的运算符全部出栈
        *(end++) = STACK_POP(stack);
    *(end++) = 0;                               // 封闭字符串
}
自行测试一下吧.....^o^...
我们最开始的问题是求值,所以下一步是把转换出来的逆波兰表达式进行求值。回到刚刚得到的结果5 2 1 2 +*-,求值就开始变得简单了。一样的,我们需要遍历逆波兰表达式的每个值,然后判断与操作的过程如下:
1. 如果是操作数,则把操作数(目前是文本)转换成值存入操作数栈。
2. 如果是二元运算符(+,-,*,/,有两个操作数),从栈中弹出两个数,进行对应运算,然后把结果放回操作数栈。
3. 如果是一元运算符(负号),从栈中弹出一个数,运算后把结果放回操作数栈。
上述过程完成后,表达式的值就会存放在栈顶,同时栈中也只有一个元素。
需要注意的是,这其中可能会被输入错误的逆波兰表达式——它们来自于错误的中缀表达式,由于上面的转换函数不会判断、出入栈函数不会判断,因此我们需要考虑栈是否溢出的问题。因此添加下面的操作栈的数据结构,和操作数的类型定义——方便未来修改,然后编写出逆波兰表达式求值的代码:
typedef  float _real;
typedef struct _OPSTACK
{
    _real       dat[STACK_DEEP];
    int	        top;                                    // 栈顶指针
}OPSTACK;

bool polandCalc(const char *end, _real *o)
{
    const char *p;
    OPSTACK     stack;
    int         d;
    _real       tpa, tpb, n, pbas, padd;
    p = end;
    STACK_INIT(stack);
    while (*p)
    {
        if (*p == CALC_Neg)
        {
            if (stack.top == 0)
                return false;
            tpa = STACK_POP(stack);             // 负号
            STACK_PUSH(stack, -tpa);
        }
        else if (IS_NUMBER(*p))                 // 数字
        {
            n = 0;
            pbas = 10;
            while (*p != COMPILE_CUT)           // 载入数字
            {
                if (*p == '.')                  // 是小数了
                {
                    pbas = (_real)0.1;
                }
                else {
                    d = *p - '0';
                    if (pbas > 1)               // >1, 那么直接叠加, 如"12.34": 1 -> 10 + 2 -> 12
                        n = n * pbas + d;
                    else                        // <1, 需要修改pbas的值, 叠加小数部分: 12 -> 12 + 0.3 -> 12.3 + 0.04
                        n = n + d * pbas, pbas *= (_real)0.1;
                }
                p++;
            }
            STACK_PUSH(stack, n);               // push数字
        }
        else {
            if (stack.top <= 1)                 // 栈中不足2个元素, 证明出了问题
                return false;
            tpa = STACK_POP(stack);
            tpb = STACK_POP(stack);
            switch (*p)
            {
            case '+':
                STACK_PUSH(stack, tpb + tpa);
                break;
            case '-':
                STACK_PUSH(stack, tpb - tpa);
                break;
            case '*':
                STACK_PUSH(stack, tpb * tpa);
                break;
            case '/':
                STACK_PUSH(stack, tpb / tpa);
                break;
            }
        }       
        p++;
    }
    *o = STACK_TOP(stack);                      // 栈目前只有一个元素了, 栈顶就是结果
    return stack.top == 1;                      // 如果不是只有一个元素, 那么肯定出问题了
}
整理一下,得到了下面的main函数:
#include <iostream>
#define  STACK_DEEP                  16     // 定义栈的大小
// 把之前的代码整理一下, 放在这里。懒得整理?全部复制过来...
int main()
{
    _real o;
    char  mid[100], end[100];
    std::cin >> mid;
    buildPoland(mid, end);
    if (polandCalc(end, &o))
        printf("%s, %f\n", end, o);
    else
        printf("原表达式输入不合法\n");
    system("pause");
    return 0;
}
至此,整个问题便解决完毕。提一下,栈的应用不单单是表达式求值。在调用函数的时候,计算机内部的栈也起到了关键的作用,甚至于操作系统的核心也有栈的身影。可以说,栈是一种很重要但是却并不复杂的数据结构。