[数据结构与算法]信息学奥赛一本通 1198：波兰表达式 | OpenJudge NOI 2.2 1696:波兰表达式

【题目链接】

ybt 1198：波兰表达式
OpenJudge NOI 2.2 1696:波兰表达式
注：ybt上描述的其实是波兰表达式，而题目中的文字都是逆波兰表达式，是笔误了，应该当做波兰表达式看。
波兰表达式是前缀表达式，逆波兰表达式是后缀表达式。

【题目考点】

【题目考点】

1. 表达式求值

2. 表达式树

表达式树：一棵表达式树可以表示一系列的运算。
表达式树中的结点包括运算符与数值

struct Node
{
	char c;//运算符
	int n;//数值
}

• 分支结点：c:运算符，n:该子树对应的表达式的值
• 叶子结点：c:'\0'，n:数值
  表达式树的值，是左子树的值和右子树的值，经过根结点运算符运算后得到的结果。

【解题思路】

解法1：前缀表达式直接求值

1. 从右向左扫描前缀表达式。
2. 遇到数字时，将数字入栈。
3. 遇到运算符时，弹出栈顶的两个数，用该运算符对它们做相应的计算，结果入栈。
4. 扫描结束后，栈顶数字就是结果。

解法2：前缀表达式构造表达式树

1. 从右向左扫描整个前缀表达式
2. 如果读到数字，那么新建数字结点入栈。
3. 如果读到运算符，则新建运算符结点p，出栈两个结点，将这两个结点的值通过p的运算符运算后得到的值存为新结点p的值，将p入栈。
4. 读完整个前缀表达式，栈中应该只剩1个结点，该结点就是表达式树的根结点，该结点的值就是表达式的值 。

解法3：递归

先将字符串处理为由结构体对象构成的前缀表达式，每个结构体对象可能是数字可能是运算符。
前缀表达式的结构为：<运算符><第一个运算单元><第二个运算单元>
每个运算单元也许是一个数字，也许是一个前缀表达式。
前缀表达式数组第一个元素的下标为si，即先将si设为1。
设函数solve()，求从第si位置开始向右遍历取到的第一个运算单元的值。每取一个元素，si向右移动一个位置。

• 如果si位置是数字，直接返回这个数字的值。
• 如果si位置是运算符，那么从p位置开始向右取两个运算单元的值，并用当前位置的运算符进行计算，得到这一运算单元的值。

【题解代码】

解法1：表达式求值

#include <bits/stdc++.h>
using namespace std;
#define N 1005
struct Node
{
    double n;
    char c;
};
Node eq[N];
int p;
double calc(double a, double b, char c)
{
    switch(c)
    {
        case '+':
            return a+b;
        case '-':
            return a-b;
        case '*':
            return a*b;
        case '/':
            return a/b;
    }
}
double solve()
{ 
    stack<double> stk;
    for(int i = p; i >= 1; --i)
    {
        if(eq[i].c)//如果是运算符 
        {//后进先出，第1运算数先出栈，第2运算数后出栈 
            double a = stk.top(); stk.pop();
            double b = stk.top(); stk.pop();
            stk.push(calc(a, b, eq[i].c));
        }
        else//数字 
            stk.push(eq[i].n);//第2运算数先入栈，第1运算数后入栈。 
    }
    return stk.top();
}
int main()
{
    char s[30];
    while(scanf("%s", s) != EOF)
    {
        if(s[0] == '+' || s[0] == '*' || s[0] == '/' || s[0] == '-' && strlen(s) == 1)//运算符 排除这是个负数 
            eq[++p].c = s[0];
        else//数字 
            eq[++p].n = atof(s);
    }
    printf("%f", solve());
    return 0;
}

解法2：构建表达式树

#include <bits/stdc++.h>
using namespace std;
#define N 1005
struct Node//表达式树中结点 
{
    double n;
    char c;
    int left, right;
}; 
Node node[N]; 
int p;
stack<int> stkEq;//用栈保存前缀表达式各元素在node中的下标，出栈的过程就是倒序遍历前缀表达式的过程。 
double calc(double a, double b, char c)
{
    switch(c)
    {
        case '+':
            return a+b;
        case '-':
            return a-b;
        case '*':
            return a*b;
        case '/':
            return a/b;
    }
}
int createTree()//根据前缀表达式stkEq来构造表达式树 返回树根 
{ 
    stack<int> stk;//保存结点地址 
    while(stkEq.empty() == false)
    {
        int i = stkEq.top(); stkEq.pop();//出栈一个元素，即为倒序遍历前缀表达式 
        if(node[i].c)//如果是运算符 
        {//后进先出，第1运算数的结点地址先出栈，第2运算数的结点地址后出栈 
            int l = stk.top(); stk.pop();
            int r = stk.top(); stk.pop();
            node[i].n = calc(node[l].n, node[r].n, node[i].c);
            node[i].left = l, node[i].right = r;
            stk.push(i);
        }
        else//数字结点直接入栈 
            stk.push(i); 
    }
    return stk.top();
}
int main()
{
    char s[30];
    while(scanf("%s", s) != EOF)
    {
        if(s[0] == '+' || s[0] == '*' || s[0] == '/' || s[0] == '-' && strlen(s) == 1)//运算符 排除这是个负数 
            node[++p].c = s[0];
        else//数字 
            node[++p].n = atof(s);
        stkEq.push(p);//先把结点的下标加到stkEq这个栈中。 
    }
    int root = createTree(); 
    printf("%f", node[root].n);
    return 0;
}

解法3：递归

#include <bits/stdc++.h>
using namespace std;
#define N 1005
struct Node
{
    double n;
    char c;
};
Node eq[N];
int p, si;//si:递归求解时的下标 
double calc(double a, double b, char c)
{
    switch(c)
    {
        case '+':
            return a+b;
        case '-':
            return a-b;
        case '*':
            return a*b;
        case '/':
            return a/b;
    }
}
double solve()
{
    int i = si++;
    if(eq[i].c)//如果是运算符 
    {
        double a = solve();//求解第2个运算单元 
        double b = solve();//求解第1个运算单元
        return calc(a, b, eq[i].c); 
    }
    else//如果是数字 
        return eq[i].n;
}
int main()
{
    char s[30];
    while(scanf("%s", s) != EOF)
    {
        if(s[0] == '+' || s[0] == '*' || s[0] == '/' || s[0] == '-' && strlen(s) == 1)//运算符 排除这是个负数 
            eq[++p].c = s[0];
        else//数字 
            eq[++p].n = atof(s);
    }
    si = 1;//eq下标从1开始 
    printf("%f", solve());
    return 0;
}