双栈计算算术表达式

1.介绍

算术表达式的计算，是比较常见的问题，但这个问题的背后隐藏着栈的思想。

这里就介绍使用两个栈来计算表达式的方法。

2. 算法

2.1 定义：

a) 建立两个栈：

一个是数据栈dataStak，用于存放数据；

一个是符号栈operatorStack，用于存放运算符；

b) 建立运算符号之间的优先级表，用于比较两个符号之间的优先级；

优先级定义为三种运算结果：>（表示高于），<（表示低于），=（表示相等）；

并且对于”(”与”)”，认为两者的优先级相同，不做任何运算；

2.2 计算条件：

a) 当同时满足b)c)d)时，可以进行计算；

b) 当前token为运算符（即不能为字符串结束符或者运算数）；

c) 符号栈非空（因为需要和栈顶元素进行优先级比较）；

d) 符号栈的栈顶元素的优先级 < 当前token；

最后操作数栈剩余的操作数就是计算的最终结果；

2.3 优先级符号表

char[,] priority = new char[6, 6] {
            //+   -    *   /  (   )
            {'>','>','<','<','<','>'}, //+
            {'>','>','<','<','<','>'}, //-
            {'>','>','>','>','<','>'}, //*
            {'>','>','>','>','<','>'}, ///
            {'<','<','<','<','<','='}, //(
            {'<','<','<','<','<','>'}  //)
        };

2.4伪码

对于每个token
if(token是数字)
{
    dataStack.push(token);
}
else
{
    switch(token与operatorStack栈顶元素进行优先级比较)
    {
        case 大于:
            dataStack.push(token);
            break;
        case 小于:
            运算符=operatorStack.pop();
            a= dataStack.pop();
            b= dataStack.pop();
                c= a运算符b;
                dataStack.push(c);
                break;
        case 等于:
                dataStack.pop();
                break;
    }
}