文章导读

【栈结构是一种特殊的线性表，线性表可以在表的任意位置插入和删除数据，而栈结构只允许在表的一端插入和删除数据，栈结构的这种特性可以解决很多实际问题。本文主要讨论用栈结构解决表达式求值问题】

表达式求值在编译程序和计算程序中被经常应用，表达式本身是一个字符序列，要实现对表达式求值，首先要能够正确解释表达式。在编程语言中，表达式是由变量、常量和运算符的组合，它执行计算并返回计算结果。在表达式中运算符作用的变量或常量称为操作数。例如，求圆面积的公式就是一个表达式，其中S、π、r为变量或常量，r的2次方可以描述为r*r。求圆面积的表达式为：

S =π* r *r;

正确地解释表达式，就是让程序扫描表达式字符序列时，从字符序列中正确解析出操作数、运算符、界限符，并按照运算规则执行运算。例如，要对下面的算术表达式求值

2*（3+5）

程序不仅要识别出2、3、5操作数，还需要识别出*、+、（、）运算符。同时还要按照算术四则运算的规则执行运算。既先乘除，后加减；从左算到右；先括号内，后括号外。

为了叙述简便，本文仅讨论简单算术表达式的求值问题，运算符也限于加、减、乘、除四中运算符，界限符仅限于小括号。读者不难将它推广到更一般的表达式上。

1、 认识栈结构

要对上面的表达式求值，可以采用算符优先法。它的实现思想是对表达式字符序列自左向右进行扫描，遇到操作数入操作数栈。遇到运算符，首先与运算符栈的栈顶运算符比较优先级，若栈顶运算符的优先级高于当前运算符，则栈顶运算符出栈并执行运算，否则将当前运算符入运算符栈，直至整个表达式求值完毕。

算符优先法算符使用的栈结构是一种特殊的线性表，限定仅在表的一端进行元素的插入和删除。当表中没有元素时，称为空栈。若给定栈：

S = (a1，a2，……，an)

则称a1是栈底元素，an是栈顶元素，表中元素按a1，a2，……，an的次序进栈，出栈的顺序是an，……，a2，a1。也就是说，栈结构的元素访问原则是后进先出，也称为后进先出的线性表的，如下图所示。

图 1 栈结构图

栈结构运算有入栈、出栈、访问栈顶元素、栈置空四种基本运算。

（1）入栈运算

该运算在长度为n的栈中，将元素置入栈顶。若栈已满，返回出错信息。

（2）出栈运算

该运算在长度为n的栈中，取出栈顶元素，并从栈中删除该元素。若栈为空，返回出错信息。

（1） 访问栈顶元素运算

该运算在长度为n的栈中，取出栈顶元素。若栈为空，返回出错信息。

（4）栈置空运算

该运算将栈置为空栈。

例1：使用Java语言建立一个栈类

package com.milihua.algorithm.lineartable;
public class MyStack {
/**
 * 声明一个存储Object对象的线性表
 * 作为栈结构
 */
private Object[] stackElem;
/**
 * 栈顶指示变量
 */
private int top;
 
/**
 * 栈初始化函数
 * maxSize为栈的长度
 */
public MyStack(int maxSize)
    {
        stackElem=new Object[maxSize];
        top=0;
    }
/**
 * 栈置空运算
 * top置为0即可
 */
public void clear()
{
    top = 0;
}
 
/**
 * 判断栈是否为空栈
 * top为0即为空栈
 */
public boolean isEmpty()
{
    return top == 0;
}
 
/**
 * 获取栈的元素个数
 * top为0即为栈的元素个数
 */
public int length()
{
    return top;
}
 
/**
 * 访问栈顶元素
 *
 */
public Object peek()
{
    if (!isEmpty())
        return stackElem[top - 1];
    else
        return null;
}
 
/**
 * 入栈运算
 *
 */
public void push(Object x) throws Exception
{
    if (top == stackElem.length)
    {
        throw new Exception("栈已满！");
    }
    else
    {
        stackElem[top++] = x;
    }
}
 
/**
 * 出栈运算
 *
 */
public Object pop() throws Exception
{
    if (top == 0)
    {
        throw new Exception("栈为空！");
    }
    else
        return stackElem[--top]; // 删除然后返回现在的栈顶
}
 
/**
 * 打印栈
 *
 */
public void display()
{
    for (int i = length() - 1; i >= 0; i--)
    {
        System.out.print(stackElem[i] + " ");
    }
    System.out.println();
}
}

MyStack栈类利用Object数组作为栈结构，存储Object类型元素。变量top是栈顶指示器，指示栈的变化。push是入栈运算，入栈之前需要判断栈是否已满，在栈未满的情况下，将元素置入栈顶，top做加一操作。pop是出栈运算，出栈之前需要判断栈是否为空，在栈不为空的情况下，返回栈顶元素，top做减一操作。peek是访问栈顶运算，与出栈运算不同的是，peek不对top做任何操作。

MyStack栈类的测试程序代码如下。

package unittest;
import com.milihua.algorithm.lineartable.MyStack;
public class StackTest {
public static void main(String[] args) throws Exception {
    // TODO Auto-generated method stub
    MyStack sqStack=new MyStack(30);
        sqStack.push(3);
        sqStack.push(6);
        sqStack.push(9);
        System.out.print("打印输出： ");
        sqStack.display();
 
        int top=(int)sqStack.peek();
        System.out.println("栈顶： "+top);
 
        sqStack.pop();
        System.out.print("弹出栈顶，打印输出： ");
        sqStack.display();
}
}

2、用算符优先法求表达式的值

表达式都是由操作数、运算符和界限符组成的。在编程语言中操作数既可以是常数，也可以是变量或常量的标识符；运算符可以分为运算符、关系运算符和逻辑运算符等三类；基本界限符有小括号、中括号和表达式结束符等。

算符优先法是根据相继出现的算符的优先级来确定运算顺序的，要比较算符的优先级，就要确定各种算符的优先级别，可以将算符间的优先级通过矩阵表示，在解析表达式过程中通过查询算符优先级矩阵获取算符间的优先关系。

我们把简单算术表达式的运算符和界限符统称为算符，它们组成一个集合op{ +，-，*，/，(，) }。集合中任意两个算符a或b的优先级至多是下面三种关系之一。

a < b    a的优先级小于b的优先级

a = b    a的优先级等于b的优先级

a > b    a的优先级大于b的优先级

在算符优先算法中，可以采用下面的矩阵定义op集合算符间的优先关系，其中a为栈顶运算符，b为当前识别的运算符。

在Java语言中，算符间的优先矩阵可以用字符类型的二维数组表示。

   /**
     * 算符集合用字符类型的数组表示
     */
    char[] operator = {'+','-','*','/','(',')'};
   
    /**
     * 算符优先级矩阵用字符类型的二维数组表示
     */
    char[][]  matrix  = {{'>','>','>','>','<','>'},
                       {'>','>','>','>','<','>'},
                       {'<','<','<','<','<','>'},
                       {'<','<','<','<','<','>'},
                       {'<','<','<','<','<','='},
                       {'>','>','>','>','=','='}
                    };

解析表达式时可以使用操作数和运算符两个栈，操作数栈用于存储操作数和运算结果，运算符栈用于存储算符。算法的基本思想是：依次读入表达式每个字符，如是操作数进操作数栈，如是运算符，需要和运算符栈的栈顶运算符比较优先级，优先级若低于栈顶运算符，首先需要处理栈顶运算符并执行相关运算后再入栈，直至整个表达式求值完毕。下面用Java语言给出算法程序代码，程序假定输入的表达式语法正确，没有对表达式语法进行检测。

package com.milihua.algorithm.lineartable;
import java.util.Stack;
public class Evaluation {
   
    /**
     * 算符集合用字符类型的数组表示
     */
    char[] operator = {'+','-','*','/','(',')'};
   
    /**
     * 算符优先级矩阵用字符类型的二维数组表示
     */
    char[][]  matrix  = {{'>','>','>','>','<','>'},
                       {'>','>','>','>','<','>'},
                       {'<','<','<','<','<','>'},
                       {'<','<','<','<','<','>'},
                       {'<','<','<','<','<','='},
                       {'>','>','>','>','=','='}
                       };
   
    /*
     * 表达式求值
     */
    public  float evaluate(String expression) {
       
        char[] tokens = expression.toCharArray();
        Stack<Float> stackOfNum = new Stack<Float>();
        Stack<Character> stackOfOps = new Stack<Character>();
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i] == ' ')
                continue;
            if (tokens[i] >= '0' && tokens[i] <= '9') {
                StringBuffer sbuf = new StringBuffer();
                while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9') {
                   sbuf.append(tokens[i++]);
                }
                i--; // 回退一位
                stackOfNum.push(Float.parseFloat(sbuf.toString()));
            }
            if( isOperator(tokens[i]) )
            {
                if( stackOfOps.empty() )
                {
                   stackOfOps.push(tokens[i]);
                }
                else
                {
                   char ch = hasPrecedence(tokens[i], stackOfOps.peek());
                   if( ch == '<' )
                   {
                       stackOfOps.push(tokens[i]);
                   }
                   else if( ch == '>' )
                   {
                       if( tokens[i] == ')' )
                       {
                           while(true)
                           {
                               if( stackOfOps.empty() )
                                   break;
                               char op = hasPrecedence(tokens[i], stackOfOps.peek());
                               if( op == '=' )
                               {
                                   stackOfOps.pop();
                                   break;
                               }
                               else
                               {
                                   stackOfNum.push(caculate(stackOfOps.pop(), stackOfNum.pop(), stackOfNum.pop()));
                               }
                           }
                       }
                       else
                       {
                           stackOfNum.push(caculate(stackOfOps.pop(), stackOfNum.pop(), stackOfNum.pop()));
                           stackOfOps.push(tokens[i]);
                       }
                   }
                }  
            }
        }
        while (!stackOfOps.empty())
        {
            stackOfNum.push(caculate(stackOfOps.pop(), stackOfNum.pop(), stackOfNum.pop()));
        }
        return stackOfNum.pop();
 
    }
   
    /**
     * 判断读入的字符是否是运算符
     */
    public boolean isOperator(char op)
    {
        for(int i = 0; i < operator.length; i++ )
        {
            if( op == operator[i] )
                return true;
        }
        return false;
    }
   
    /**
     * 获取运算符在数组中的索引
     */
    public int getOperator(char op)
    {
        for(int i = 0; i < operator.length; i++ )
        {
            if( op == operator[i] )
                return i;
        }
        return -1;
    }
   
    /**
     * 判断op1和op2的优先级
     *
     */
    public  char  hasPrecedence(char op1, char op2) {
       
        int suffixop1 = getOperator(op1);
        int suffixop2 = getOperator(op2);
        if( suffixop1 == -1 || suffixop2 == -1 )
            return 0;
        return matrix[suffixop1][suffixop2];
    }
 
    /**
     * 执行运算
     *
     */
    public  float caculate(char op, float b, float a) {
        switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            if (b == 0) {
                throw new UnsupportedOperationException("Cannot divide by zero");
            }
            return a / b;
        }
        return 0;
 
    }
 
    /**
     * 输出栈
     *
     */
    public void display(Stack  s)
    {
        for( int i = 0; i < s.size(); i++ )
        {
            System.out.print(s.get(i) + " ");
        }
        System.out.println();
    }
}

evaluate函数是算法的核心，基本体现了前面给出的算法思想。其中对小括号做了特殊处理，当遇到算符')'时，需要对算符栈连续执行出栈操作，并执行相关运算，直至与栈顶运算符优先级相等或者栈已空。

hasPrecedence函数用于判断两个算符的优先级关系，算符的优先级矩阵由matrix给出，函数返回矩阵给出的优先级关系。

测试程序代码如下。

package unittest;
import com.milihua.algorithm.lineartable.Evaluation;
import com.milihua.algorithm.lineartable.Expression;
public class EvluationTest {
 
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Evaluation  evaluation = new Evaluation();
    System.out.println(evaluation.evaluate("2*(3+5)")); 
    System.out.println(evaluation.evaluate("100 * 2 + 12"));
    System.out.println(evaluation.evaluate("100 * ( 2 + 12 )"));
    System.out.println(evaluation.evaluate("100 * ( 2 + 12 ) / 14"));
    System.out.println(Expression.evaluate("5 * ( 6 + 12 ) * 5 - 12"));
    System.out.println(Expression.evaluate("3+12*18-60*15+3*(3+2)"));
}
 
}

文章小结

（1）栈结构是一种特殊的线性表，限定仅在表的一端进行元素的插入和删除。执行运算的一端称为栈顶，当表中没有元素时，为空栈。插入元素在栈顶插入，称为入栈，删除元素称为出栈，具体运算规则是先返回栈顶元素，然后再删除栈顶元素。

（2）算符优先法的实现思想是对表达式字符序列自左向右进行扫描，遇到操作数入操作数栈。遇到运算符，首先与运算符栈的栈顶运算符比较优先级，若栈顶元素符的优先级高于当前运算符，则栈顶运算符出栈并执行运算，否则将当前运算符入运算符栈，直至整个表达式求值完毕。