欢迎观临
路漫漫其修远兮,吾将上下而求索

前缀、中缀、后缀表达式

一、简介

前缀表达式、中缀表达式、后缀表达式都是数学中四则运算的表达方式。

日常生活中我们最常见的形如(a+b)xc表达式即中缀表达式,即操作符位于左右操作数的中间。但是计算机中利用中缀表达式计算求值则比较麻烦,需要将中缀表达式转换成表达式树,然后再递归进行计算,时间和空间复杂度都比较高。

为了便于计算机运算,波兰数学家Jan Lukasiewicz发明了前缀表达式,将操作符写在操作数的前面(如x+abc),这样可以将四则运算用到的结构由树变成线性结构,大大提升了运算效率。为了纪念,人们将前缀称为波兰式

但是因为将中缀表达式转变为前缀表达式,以及前缀表达式求值,都需要从右往左(从后往前)扫描表达式,不符合日常习惯,所以基于和前缀表达式类似的逻辑,又产生了后缀表达式,又称为逆波兰式

计算机中通常采用的都是后缀表达式。

二、中缀表达式转换后缀表达式

  1. 利用栈存放操作符,记栈为S1;
  2. 从左往右扫描中缀表达式,当读到一个操作数时,立即将其输出;
  3. 当读到一个操作符+-x()时:
    • 如果是(时,直接入栈S1;
    • 如果是+-x,则比较该操作符与栈顶优先级,如果该操作符比栈顶优先级高或者栈顶是(,则直接入栈S1;否则弹出栈顶元素到输出,然后继续比较;其中优先级:( > x > + = -
    • 如果是),则将栈S1元素弹出到输出,直到遇到一个(为止;此时将(移除栈S1但不输出;
  4. 当扫描完成,将栈S1中的元素挨个弹出到输出中。

例将中缀式1+((2+3)×4)-5转为后缀式:

扫描元素 栈S1 输出 说明
1 1 数字直接输出
+ + 1 栈空,+直接入栈
( +( 1 (直接入栈
( +(( 1 (直接入栈
2 +(( 1 2 数字直接输出
+ +((+ 1 2 栈顶是(+直接入栈
3 +((+ 1 2 3 数字直接输出
) +( 1 2 3 + ),弹出栈中元素直到遇到(
x +(x 1 2 3 + 栈顶是(x直接入栈
4 +(x 1 2 3 + 4 数字直接输出
) + 1 2 3 + 4 x ),弹出栈中元素直到遇到(
1 2 3 + 4 x + +-优先级相同,所以弹出+,压入-
5 1 2 3 + 4 x + 5 数字直接输出
完成 1 2 3 + 4 x + 5 – 将栈中元素挨个弹出到输出

三、后缀表达式求值

  1. 利用栈存放操作数和中间结果,记栈为S1;
  2. 从左往右扫描后缀表达式,当读到一个操作数时,将其压入栈S1中;
  3. 当读到一个操作符时,从栈中弹出两个操作数,并用该操作符进行计算,再将所得结果压入栈中;
  4. 当扫描完成,栈中剩下唯一一个元素就是计算结果。

以后缀式1 2 3 + 4 x + 5 -为例:

扫描元素 栈S1 说明
1 1 数字直接入栈
2 1 2 数字直接入栈
3 1 2 3 数字直接入栈
+ 1 5 弹出2 3,并将2+3结果入栈
4 1 5 4 数字直接入栈
x 1 20 弹出 5 4,并将5x4结果入栈
+ 21 弹出1 20,并将1+20结果入栈
5 21 5 数字直接入栈
16 弹出21 5,并将21-5结果入栈
完成 16 栈中最后元素即为表达式结果

示例代码:

#include <string>
#include <vector>
#include <stack>

using namespace std;

//辅助函数
inline bool isdigit(char c) {
    return c- '0' >= 0 && c - '0' <= 9;
}

inline bool isOperator(const string& str) {
    return str.size() == 1 && !isdigit(str[0]);
}

//解析中缀表达式字符串
vector<string> parseInfixExpression(const string& exp) {
    vector<string> tokens;
    for(size_t i(0); i < exp.size(); ++i) {
        char c = exp[i];
        if(c == ' ') {
            continue;
        }
        switch(c) {
            case '+':
            case '*':
            case '/':
            case '(':
            case ')': {
                tokens.push_back("" + c);
                break;
            }
            case '-': {
                if(i > 0 && (exp[i-1] == ')' || isdigit(exp[i-1]))) {
                    //作减号使用
                    tokens.push_back("" + c);
                } else {
                    //作负号使用
                    tokens.push_back("#");
                }
                break;
            }
            default: {
                string temp = "" + c;
                while(i+1 < exp.size() && isdigit(exp[i+1])) {
                    temp += exp[++i];
                }
                tokens.push_back(temp);
                break;
            }
        }
    }
    return tokens;
}

int getPriority(const string& op) {
    int priority = 0;
    if(op=="#")
        priority = 3;  
    else if(op=="*"||op=="/")
        priority = 2;
    else if(op=="+"||op=="-")
        priority = 1;
    else if(op=="(")
        priority = 0;
    return priority;
}

//中缀表达式序列转后缀表达式序列
vector<string> infixToPostfix(const vector<string> infixTokens) {
    vector<string> postfixTokens;
    stack<string> opStack;
    for(size_t i(0); i < infixTokens.size(); ++i) {
        const string& t = infixTokens[i];
        if(!isOperator(t)) {
            postfixTokens.push_back(t);
        } else if (t == "(") {
            opStack.push(t);
        } else if (t == "#" || t == "+" || t == "-" || t == "*" || t == "/") {
            int priToken = getPriority(t);
            while(!opStack.empty()) {
                int priTop = getPriority(opStack.top());
                if(priToken <= priTop) {
                    postfixTokens.push_back(opStack.top());
                    opStack.pop();
                } else {
                    break;
                }
            }
            opStack.push(t);
        } else if (t == ")") {
            while(!opStack.empty()) {
                if(opStack.top() == "(") {
                    opStack.pop();
                    break;
                }
                postfixTokens.push_back(opStack.top());
                opStack.pop();
            }
        }
    }
    while(!opStack.empty()) {
        postfixTokens.push_back(opStack.top());
        opStack.pop();
    }
    return postfixTokens;
}

//计算后缀表达式序列的值
int calcPostfix(const vector<string>& tokens) {
    stack<int> resStack;
    for(size_t i(0); i < tokens.size(); ++i) {
        const string& t = tokens[i];
        if(!isOperator(t)) {
            resStack.push(atoi(t.c_str()));
        } else if (t == "#") {
            int temp = resStack.top();
            resStack.pop();
            resStack.push(0 - temp);
        } else if (t == "+") {
            int r = resStack.top();
            resStack.pop();
            int l = resStack.top();
            resStack.pop();
            resStack.push(l + r);
        } else if (t == "-") {
            int r = resStack.top();
            resStack.pop();
            int l = resStack.top();
            resStack.pop();
            resStack.push(l - r);
        } else if (t == "*") {
            int r = resStack.top();
            resStack.pop();
            int l = resStack.top();
            resStack.pop();
            resStack.push(l * r);
        } else if (t == "/") {
            int r = resStack.top();
            resStack.pop();
            int l = resStack.top();
            resStack.pop();
            resStack.push(l / r);
        }
    }
    return resStack.top();
}
赞(0) 打赏
未经允许不得转载:云海鹰影博客 » 前缀、中缀、后缀表达式
分享到: 更多 (0)

欢迎留言 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏