C++如何实现中缀表达式转化为后缀表达式

这篇文章将为大家详细讲解有关c++如何实现中缀表达式转化为后缀表达式，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

1.题目描述

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右进行（不用考虑运算符的优先级）。

如：中缀表达式 3*(5–2)+7 对应的后缀表达式为：352-*7+ 。

请将给出的中缀表达式转化为后缀表达式并输出。

2.输入输出

输入样例: 

2+4*8+(8*8+1)/3

输出样例:

248*+88*1+3/+

3.解题思路

对于中缀表达式转换为后缀表达式，我们需要用以下步骤来解决这个问题：

初始化一个个栈：运算符栈S1

从左往右开始扫描中缀表达式

I.遇到数字，直接输出

II.遇到运算符：

• 若为 '('  直接入栈

• 若为 ')'  将符号栈中的元素依次出栈并输出,直到 '(', '(' 只出栈，不输出

• 若为其他符号，将符号栈中的元素依次出栈并将其输出，直到遇到比当前符号优先级更低的符号或者 '('。将当前符号入栈。

• 扫描完后，将栈中剩余的符号依次输出。

4.样例解析 

下面以 a + b * c +(d * e + f) * g 为例子来讲讲计算机的转换过程。

从左向右开始遍历表达式，首先遇到a, 直接将其输出

此时输出 ：a

栈的情况：空

继续遍历表达式，遇到+，此时栈空，则将其放入栈中

此时输出 ：a

栈的情况：+

继续遍历表达式，遇到b，直接将其输出

此时输出 ：a b

栈的情况：+

继续遍历表达式，遇到*，因为*的优先级大于栈顶的+，所以将*入栈

此时输出 ：a b

栈的情况：+*

继续遍历表达式，遇到c，直接将其输出

此时输出 ：a b c

栈的情况：+*

继续遍历表达式，遇到+, 因为+的优先级低于栈顶的*，所以将栈顶的*弹出；然后新的栈顶元素的+与当前的+优先级相同，所以也要将+弹出；然后栈空了，将现在这个+放入栈中

此时输出 ：a b c * + 

栈的情况：+

继续遍历表达式，遇到(，直接将其放入栈中，不遇到)不会将(弹出。

此时输出为：a b c * + 

栈的情况为：+(

继续遍历表达式，遇到d，直接将其输出

此时输出为：a b c * + d

栈的情况为：+(

继续遍历表达式，遇到*，因为栈顶为(,不遇到)不将(弹出,故直接将*放入栈中。

此时输出为：a b c * + d

栈的情况为：+(*

继续遍历表达式，遇到e，直接将其输出

此时输出为：a b c * + d e

栈的情况为：+(*

继续遍历表达式，遇到+，因为+比栈顶*的优先级低，故将*弹出；新的栈顶元素为(,不遇到)不弹出(,故将+放入栈中。

此时输出为：a b c * + d e *

栈的情况为：+(+

继续遍历表达式，遇到f，直接将其输出

此时输出为：a b c * + d e *  f

栈的情况为：+(+

继续遍历表达式，遇到),直接将栈中元素依次弹出并输出直到遇到(为止，注意：(弹出但不输出。

此时输出为：a b c * + d e *  f + 

栈的情况为：+

继续遍历表达式，遇到*，因为*的优先级大于栈顶元素+的优先级，故直接将*入栈。

此时输出为：a b c * + d e *  f + 

栈的情况为：+ * 

继续遍历表达式，遇到g，直接将其输出。

此时输出为：a b c * + d e *  f + g

栈的情况为：+ * 

继续遍历表达式，为空，遍历结束。将栈内元素依次弹出。

此时输出为：a b c * + d e *  f + g * +

栈的情况为：空

至此，中缀表达式转后缀已经全部完成，结果为 a b c * + d e *  f + g * +

5.代码实现

5.1.优先级确认

int priority(char op){    int priority;    if(op == '*' || op == '/') priority = 2;    if(op == '+' || op == '-') priority = 1;    if(op == '(') priority = 0;    return priority;}

5.2.转换函数

//引用符号提高转换效率void Trans(string &str, string &str1){    stack<char> s;    int i;    for(i = 0; i < str.size(); i ++ )    {        //是数字的情况下直接输出        if(str[i] >= '0' && str[i] <= '9' || str[i] >= 'a' && str[i] <= 'z')        {            str1 += str[i];        }        else //不是数字的情况分类讨论进行判断        {            //栈为空时直接入栈            if(s.empty()) s.push(str[i]);            //左括号入栈            else if(str[i] == '(') s.push(str[i]);            //如果是右括号，只要栈顶不是左括号，就弹出并输出            else if(str[i] == ')')            {                while(s.top() != '(')                {                    str1 += s.top();                    s.pop();                }                //弹出左括号，但不输出                s.pop();            }            else             {                //栈顶元素的优先级大于等于当前的运算符，就将其输出                while(priority(str[i]) <= priorty(s.top()))                {                    str1 += s.top();                    s.pop();                    //栈为空，停止                    if(s.empty()) break;                }                s.push(str[i]);            }        }    }    //最后，如果不为空，就把所以的元素全部弹出    while(!s.empty())    {        str1 += s.top();         s.pop();    }}

#include <iOStream>#include <cstring>#include <stack> using namespace std; int priority(char op){    int priority;    if(op == '*' || op == '/') priority = 2;    if(op == '+' || op == '-') priority = 1;    if(op == '(') priority = 0;    return priority;} //引用符号提高转换效率void Trans(string &str, string &str1){    stack<char> s;    int i;    for(i = 0; i < str.size(); i ++ )    {        //是数字的情况下直接输出        if(str[i] >= '0' && str[i] <= '9' || str[i] >= 'a' && str[i] <= 'z')        {            str1 += str[i];        }        else //不是数字的情况分类讨论进行判断        {            //栈为空时直接入栈            if(s.empty()) s.push(str[i]);            //左括号入栈            else if(str[i] == '(') s.push(str[i]);            //如果是右括号，只要栈顶不是左括号，就弹出并输出            else if(str[i] == ')')            {                while(s.top() != '(')                {                    str1 += s.top();                    s.pop();                }                //弹出左括号，但不输出                s.pop();            }            else             {                //栈顶元素的优先级大于等于当前的运算符，就将其输出                while(priority(str[i]) <= priorty(s.top()))                {                    str1 += s.top();                    s.pop();                    //栈为空，停止                    if(s.empty()) break;                }                s.push(str[i]);            }        }    }    //最后，如果不为空，就把所以的元素全部弹出    while(!s.empty())    {        str1 += s.top();         s.pop();    }} int main(){    //输入前缀表达式    string infix;    string postfix;    cin >> infix;        Trans(infix, postfix);        cout << postfix << endl;    return 0;}

关于“C++如何实现中缀表达式转化为后缀表达式”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。