前缀表达式的计算

前面我们曾对《后缀表达式的计算》做过讨论。后缀表达式的计算过程是首先设定一个操作数栈，顺序扫描整个后缀表达式，如果遇到操作数，则将操作数压栈；如果遇到操作符，则从操作数栈中弹出相应的操作数进行运算，并将运算结果进行压栈。当将整个后缀表达式扫描完毕时，操作数栈中应该只有一个元素，该元素的值即为后缀表达式的计算结果。

对于一个后缀表达式：

1 2 3 + -

其对应的前缀表达式为：

-1 + 2 3

前缀表达式的计算方法与后缀表达式的计算方法类似。对前缀表达式从后向前扫描，设定一个操作数栈，如果是操作数，则将其直接入栈，如果是操作符，则从栈中弹出操作符对应的操作数进行运算，并将计算结果压栈。直至从右到左扫描完毕整个前缀表达式，这时操作数栈中应该只有一个元素，该元素的值则为前缀表达式的计算结果。

具体前缀表达式的计算程序如下：

// 计算前缀表达式
#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
#include <string>
using namespace std;

void GetPrefix(vector<string>& prefix)
{
    prefix.clear();
    string line, tmp;
    getline(cin, line);
    istringstream sin(line);
    while (sin >> tmp)
    {
        prefix.push_back(tmp);
    }
}

bool IsOperator(const string& op)
{
    return op == "+" || op == "-" || op == "*" || op == "/";
}

double CalPrefix(const vector<string>& prefix)
{
    double ret = 0.0;
    stack<double> opeStk;
    for (int i = prefix.size() - 1; i >= 0; --i)
    {
        if (!IsOperator(prefix[i]))
        {
            opeStk.push((double)atof(prefix[i].c_str()));
        }
        else
        {
            double a = opeStk.top();
            opeStk.pop();
            double b = opeStk.top();
            opeStk.pop();
            double c = 0.0;

            switch (prefix[i][0])
            {
            case '+':
                c = a + b;
                opeStk.push(c);
                break;

            case '-':
                c = a - b;
                opeStk.push(c);
                break;

            case '*':
                c = a * b;
                opeStk.push(c);
                break;

            case '/':
                c = a / b;
                opeStk.push(c);
                break;

            default:
                break;
            }
        }
    }

    if (opeStk.size() == 1)
    {
        return opeStk.top();
    }
    else
    {
        return -1000000000.0;
    }
}

int main()
{
    vector<string> prefix;
    while (true)
    {
        GetPrefix(prefix);
        cout << CalPrefix(prefix) << endl << endl;
    }
    return 0;
}

下面我们比较一下前缀表达式的计算与后缀表达式计算的联系和区别：

	前缀表达式计算	后缀表达式计算
扫描顺序	从右到左	从左到右
栈	操作数栈	操作数栈
遇到操作数时	压栈	压栈
遇到操作符时	出栈	出栈
出栈的顺序	先弹出操作数a，后弹出b	先弹出操作数b，后弹出a
结果	操作数栈中唯一元素的值	操作数栈中唯一元素的值

以上是讨论了前缀表达式的计算，并与后缀表达式的计算进行了比较。后续我们将进一步讨论中缀表达式如何转换为前缀表达式，并且结合之前的中缀表达式转换为后缀表达式的算法，比较两者之间的关系和区别，从而对中缀、前缀、后缀这三种表达式的计算以及相互之间的转换有更深的理解。

另外，我们之前讨论过关于四则四则运算表达式的语法分析，通过语法分析我们可以得到四则运算表达式对应的递归二叉树，进而可以根据该二叉树得到任意的前缀、中缀、后缀表达式，其实质即使二叉树的前序、中序、后序遍历。针对前缀、中缀、后缀三种表达式，我们可以通过对其进行语法分析，得到对应的递归二叉树，进而对二叉树进行前序、中序、后序遍历，得到每种表达式对应的其他两种形式的表达式。这种通过递归下降语法分析而实现的四则运算表达式在前缀、中缀、后缀三种形式之间的转换很好的解决了表达式在三种形式间的转换问题。