中缀表达式变前缀表达式（波兰式）并求值

小咪咪 2022-05-30 10:47 225阅读 0赞

1.先介绍一种简单的数学小技巧，可以快速写出一个算式的前缀表达式

eg:1+2-3\*（4-5）

我们只需要在正确的计算顺序上加上适当的辅助括号，再把运算符号提到相应的括号外，就可以方便地得到前缀表达式了

具体操作如下：（（1+2）-（3\*（4-5）））    把符号提到括号外：-（+（1 2）\*（3-（4 5）））

最后去掉辅助括号，就得到了相应的前缀表达式：- + 1 2 \* 3 - 4  5【这个方法也适合后缀表达式哦】

2.上面只是简单的数学小技巧，下面就要真刀真枪地从算法的角度（用栈的方法实现）实现了

大致思路：定义两个栈，一个符号栈存运算符，一个数字栈存数字和处理后的字符，将算式从后往前读入栈中。

讲解以算式:1+2-3\*（4-5）为例

其实，中缀表达式转前缀表达式只需要注意以下四点，问题就迎刃而解：

当符号栈为空的时候，符号直接放入符号栈中

符号栈中元素：）

数字栈中元素：5

当符号栈中有元素时，

（1）若符号栈中元素是')'，可以直接入符号栈

符号栈中元素：） -

数字栈中元素：5 4

（2）若将要入符号栈的是'('，说明括号里的内容输入完了，此时可以把')’和'('之间的所有符号出符号栈进数字栈

符号栈中元素：         【括号不是实际符号，处理掉】

数字栈中元素：5 4 -

接下来按照原理：

符号栈中元素：\*

数字栈中元素：5 4 - 3

(3)若将要入栈的符号运算优先级比符号栈栈顶符号的优先级低，则将栈顶元素出符号栈入数字栈，直到将入栈的符号优先级不再比符号栈优先级低【优先级可以相同】，再把将要入栈的符号入符号栈【  ')’比较例外，不用比较优先级，直接进符号栈】

符号栈中元素：-

数字栈中元素：5 4 - 3 \*

接下来按照原理：

符号栈中元素：- +

数字栈中元素：5 4 - 3 2 1

最后一步，把符号栈剩余符号全部入数字栈5 4 - 3 \* 2 1 + -

出栈后，就得到了完整的前缀表达式：- + 1 2 \* 3 - 4  5

3.求值问题

求值问题相对简单，因为把算式转化为前缀表达式就是为了方便求值的嘛

我们观察这个前缀表达式：- + 1 2 \* 3 - 4  5

只要从后往前，两个操作数两个操作数地运算【运算符用最接近两数的运算符】，就能得到算式值了

即：4-5=-1 ，3\*（-1）=-3， 1+2=3 ，3-（-3）=6

具体代码如下：

\#include<iostream>  
\#include<algorithm>  
\#include<stack>  
\#include<stdio.h>  
\#include<string>  
using namespace std;  
void caozuo(stack<char>&s, stack<char>&t) \{  
    while (s.top() != ')') \{  
        t.push(s.top());  
        s.pop();  
    \}  
    s.pop();//把右括号pop掉  
\}  
void caozuo2(char temp, stack<long long int>&t) \{  
    long long int a = t.top();  
    t.pop();  
    long long int b = t.top();  
    t.pop();  
    switch (temp) \{  
    case '+':t.push(a + b); break;  
    case '-':t.push(a - b); break;  
    case '\*':t.push(a \* b); break;  
    \}  
\}  
int main() \{  
    string str;  
    int num = 1;  
    while (cin >> str) \{  
        stack<char>s1;  
        stack<char>s2;  
        int len = str.length();  
        while (len) \{  
            len--;  
            char temp = str\[len\];  
            if (temp == ')')s1.push(temp);  
            else if (temp == '(')caozuo(s1, s2);  
            else if (temp == '+' || temp == '-') \{  
                if (s1.empty())s1.push(temp);  
                else \{  
                    if (s1.top() == ')')s1.push(temp);  
                    else if (s1.top() == '+' || s1.top() == '-')s1.push(temp);  
                    else if (s1.top() == '\*') \{  
                        while (!s1.empty() && (s1.top() == '\*')) \{  
                            s2.push(s1.top());  
                            s1.pop();  
                        \}  
                        s1.push(temp);  
                    \}  
                \}  
            \}  
            else if (temp == '\*') \{ s1.push(temp); \}  
            else \{  
                while (len >= 0 && str\[len\] >= '0'&&str\[len\] <= '9') \{ s2.push(str\[len\]); len--; \}  
                len++;  
                s2.push(' ');  
            \}  
        \}  
        while (!s1.empty()) \{  
            s2.push(s1.top());  
            s1.pop();  
        \}  
        string c1;  
        while (!s2.empty()) \{  
            /\*if (s2.top() != ' ')  
            cout << s2.top();\*/  
            c1 += s2.top();  
            s2.pop();  
        \}  
        //cout << endl;  
        //cout << c1 << endl;  
        string ctemp = c1;  
        stack<char>c2temp;  
        //cout << ctemp<< endl;  
        for (int i = ctemp.length() - 1;i >0;i--)  
        \{  
            if (ctemp\[i\] == '+' || ctemp\[i\] == '-' || ctemp\[i\] == '\*') \{  
                c2temp.push(ctemp\[i\]);  
                c2temp.push(' ');  
            \}  
            else c2temp.push(ctemp\[i\]);  
        \}  
        printf("Case %d:\\n", num++);  
        c2temp.push(ctemp\[0\]);  
                if(c2temp.top()==' ')c2temp.pop();//"11"单独数字也是算式  
        while (!c2temp.empty()) \{  
            cout << c2temp.top();  
            c2temp.pop();  
        \}  
        cout << endl;  
        stack<long long int>c2;  
        int i = c1.length();  
        while (i) \{  
            i--;  
            if (c1\[i\] == ' ')continue;  
            else if (c1\[i\] >= '0'&&c1\[i\] <= '9') \{  
                long long int x = 0, y = 1;  
                while (c1\[i\] >= '0'&&c1\[i\] <= '9') \{  
                    x = x + (c1\[i\] - '0')\*y;  
                    y \*= 10;  
                    i--;  
                \}  
                i++;  
                c2.push(x);  
            \}  
            else caozuo2(c1\[i\], c2);  
        \}  
        cout << c2.top() << endl;  
    \}  
\}

第一次写博客，有错误或不足之处还请谅解![微笑][smile.gif]【求值的算法只适合整数算式求值问题】

[smile.gif]: /images/20220530/301f3e655d6a49b4b19c243dcc7a47b2.png