计算机如何进行表达式求值?

例:算术表达式:5+6/2345+6/2-3*4

运算时有优先次序,使得运算符后跟着的操作数并不一定参与这个运算

算术表达式

算术表达式由两类对象构成:

  • 运算数,如:2、3、4
  • 运算符号,如:+,,,/+,-,*,/
  • 不同运算符号优先级不同

后缀表达式

  • 中缀表达式:运算符号位于两个运算数之间,如:a+b*c-d/e
  • 后缀表达式:运算符号位于两个运算数之后,如:abc*+de/-

例:66 22 / 33 4- 4 2+=?2 *+=?

求值策略和方法

后缀表达式求值策略:从左向右“扫描”,逐个处理运算数和运算符号

  • 遇到运算数时怎么办?如何“记住”目前还不参与运算的数?
    • 当碰到运算数时,存储当前的运算数
  • 遇到运算符号怎么办?对应的运算数是什么?
    • 根据运算符(一元、二元、三元)所需的运算数将最近记住的几个运算数拿来运算

中追表达式求值策略:将中缀表达式转换为后缀表达式,再求值

  • 如何将中缀表达式转换为后缀表达式?
  • 例:2 + 9 / 352\space+\space9\space/\space3-5 —> 2 9 3 /+5 2\space9\space3 \space/ + 5\space -
    • 运算数之间相对顺序不变
    • 运算符号顺序发生改变
      • 需要存储“等待中”的运算符号
      • 要将当前运算符号与“等待中”的最后一个运算符号比较
      • 有括号怎么办?

表达式求值问题的启示:需要某种存储方法,能顺序存储运算数,并在需要时“倒序”输出

后缀表达式求值方法:应用堆栈(T(n)=O(n))(T(n)=O(n))
基本过程:从左到右读入后缀表达式的各项(运算符或运算数)时,碰到:

  • 运算数:压栈
  • 运算符:从堆栈中弹出适当数量的运算数,计算结果并入栈
  • 最后,堆栈顶的元素就是表达式的结果值

中注表达式求值:应用堆栈将中缀表达式转换为后缀表达式,再利用堆栈求值
基本过程:从头到尾读取中追表达式的每个对象,对不同对象按不同情景处理(T(n)=O(n))

  • 运算数:直接输出
  • 左括号:压入堆栈
    • 左括号压栈后,相当于优先级降到最低
  • 右括号:将栈顶运算符弹出并输出,直到遇到左括号(出栈,不输出);
  • 运算符:
    • 若优先级大于栈顶运算符时,将其压栈
    • 若优先级小于等于栈顶运算符时,将栈顶运算符弹出并输出;依次与剩下的栈顶运算符比较,直到该运算符大于栈顶运算符优先级为止,将该运算符压栈
  • 若各对象处理完毕,则把堆栈中存留的运算符一并输出

堆栈

堆栈/栈(Stack)”:具有一定操作约束的线性表

  • 只在一端(栈顶,Top)做插入、删除
  • 插入数据:入栈(Push)
  • 删除数据:出栈(Pop)
  • 后入先出:Last In First Out(LIFO)

现实中最能体现堆栈结构的实例:放碗

  • 后放的碗只能叠在先放的碗上面,取碗时必须先取完放在上面的碗才能取下面的碗

堆栈的抽象数据类型描述

类型名称:堆栈(Stack)
数据对象集:一个有0个或多个元素的有穷线性表
操作集:长度为Maxsize的堆栈S ∈ Stack,堆栈元素item ∈ ElementType
Stack CreateStack(int Maxsize):生成空堆栈,其最大长度为Maxsize;
int IsFull(Stack S,int Maxsize):判断堆栈S是否已满;
void Push(Stack S,ElementType item):将元素item压入堆栈
int IsEmpty(Stack S):判断堆栈S是否为空;
ElementType Pop(Stack S):删除并返回栈顶元素;

Push和Pop可以穿插交替进行;
例:按照顺序进行如下操作

  • Push(S,A),Push(S,B),Push(S,C),Pop(S),Pop(S),Pop(S)
    • 堆栈输出为:在ABC的所有排列中只有CAB是不可能产生的
  • Push(S,A),Pop(S),Push(S,B),Push(S,C),Pop(S),Pop(S)
    • 堆栈输出为:ACB
  • 如果三个字符按ABC顺序压入堆栈,在ABC的所有排列中只有CAB是不可能产生的

堆栈的顺序存储实现

堆栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的下标变量组成

#define MaxSize<储存数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode
{
    ElementType Data[MaxSize];
    int Top;                               //Top为-1时栈空,Top为MaxSize-1时栈满
};

堆栈的链式存储实现

堆栈的链式存储结构实际上就是一个单链表,称为链栈

插入和删除操作只能在链栈的栈顶进行              //栈顶指针Top实际就是链表头结点的指针,因为头结点知道下一个元素的位置,而下一个不知道上一个的位置
typedef struct SNode *Stack;              //栈顶指针
struct SNode
{
    ElementType Data;
    struct SNode *Next;                   //指向链表下一个结点的指针
};

堆栈的主要应用

  • 表达式求值
  • 函数调用及递归实现
  • 深度优先遍历
  • 回溯算法
  • ……

堆栈顺序存储演示

//以下两部分顺序存储和链式存储代码均来自浙江大学数据结构课程
#include<cstdio>
#include<cstdlib>
#define ERROR -1
#define MaxSize 1000
typedef int Position;
typedef int ElementType;
struct SNode {
    ElementType *Data; /* 存储元素的数组 */
    Position Top;      /* 栈顶指针 */
    int maxSize;       /* 堆栈最大容量 */
};
typedef struct SNode *Stack;

Stack CreateStack( int maxSize )
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S->Top = -1;
    S->maxSize = MaxSize;
    return S;
}

bool IsFull( Stack S )
{
    return (S->Top == S->maxSize-1);
}

bool Push( Stack S, ElementType X )
{
    if ( IsFull(S) ) {
        printf("堆栈满");
        return false;
    }
    else {
        S->Data[++(S->Top)] = X;                                   //元素压入到栈顶下面一个位置(Top+1)
        return true;
    }
}

bool IsEmpty( Stack S )
{
    return (S->Top == -1);
}

ElementType Pop( Stack S )
{
    if ( IsEmpty(S) ) {
        printf("堆栈空");
        return ERROR; /* ERROR是ElementType的特殊值,标志错误 */
    }
    else 
        return ( S->Data[(S->Top)--] );                             //出栈时先出栈顶元素,再将Top下标-1
}
/*
    例:用一个数组实现两个堆栈,要求最大地利用数组空间,使数组只要有空间入栈操作就可以成功
    较为高效的做法是将两个栈分别从数组的两头开始向中间生长,当两个栈的栈顶指针相遇时,表示两个栈都满了
*/
typedef struct DStack           //定义两个栈
{
    ElementType *Data;
    int Top1,Top2;      //两个栈顶指针
}ds,*dstack;
dstack CreateDS( int maxSize )
{
    dstack S = (dstack)malloc(sizeof(ds));
    S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S->Top1 = -1;
    S->Top2 = MaxSize;
    return S;
}
/* 此时入栈操作改为: */
void Push(struct DStack *PtrS,ElementType item,int Tag)              //如果没事先定义Stack指针的话,这里需要传入结构体DStack的指针
{
    if(PtrS->Top1-PtrS->Top2==1) printf("两个堆栈均满");               //当两个指针挨上的时候说明两个栈满了
    else
    {
        if(Tag==1)PtrS->Data[++PtrS->Top1]=item;               
        else PtrS->Data[--PtrS->Top2]=item;
    }
    return;
}
/* 出栈操作改为: */
ElementType Pop(struct DStack *PtrS,int Tag)
{
    if(Tag==1)
    {
        if(PtrS->Top1==-1)
        {
            printf("堆栈1空");
            return ERROR;                                        
        }
        else return PtrS->Data[PtrS->Top1--];
    }
    else
    {
        if(PtrS->Top2==MaxSize)
        {
            printf("堆栈2空");
            return ERROR;
        }
        else return PtrS->Data[PtrS->Top2++];
    }
}

堆栈链式存储演示

#include<cstdio>
#include<cstdlib>
#define ERROR -1
typedef struct SNode *PtrToSNode;
typedef int ElementType;
struct SNode {
    ElementType Data;
    PtrToSNode Next;
};
typedef PtrToSNode Stack;

Stack CreateStack( ) 
{ /* 构建一个堆栈的头结点,返回该结点指针 */
    Stack S;

    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

bool IsEmpty ( Stack S )
{ /* 判断堆栈S是否为空,若是返回true;否则返回false */
    return ( S->Next == NULL );                                 //堆栈为空返回1,不为空返回0
}

bool Push( Stack S, ElementType X )
{ /* 将元素X压入堆栈S */
    PtrToSNode TmpCell;

    TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
    TmpCell->Data = X;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
    return true;
}

ElementType Pop( Stack S )  
{ /* 删除并返回堆栈S的栈顶元素 */
    PtrToSNode FirstCell;
    ElementType TopElem;

    if( IsEmpty(S) ) {
        printf("堆栈空"); 
        return ERROR;
    }
    else {
        FirstCell = S->Next; 
        TopElem = FirstCell->Data;
        S->Next = FirstCell->Next;
        free(FirstCell);
        return TopElem;
    }
}