亲宝软件园·资讯

展开

C++中缀转后缀表达式

玄澈_ 人气:0

1.题目描述

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

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

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

2.输入输出

输入样例: 

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

输出样例:

248*+88*1+3/+

3.解题思路

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

1.初始化一个个栈:运算符栈S1

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

I.遇到数字,直接输出

II.遇到运算符:

4.样例解析 

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

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

此时输出 :a

栈的情况:空

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

此时输出 :a

栈的情况:+

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

此时输出 :a b

栈的情况:+

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

此时输出 :a b

栈的情况:+*

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

此时输出 :a b c

栈的情况:+*

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

此时输出 :a b c * + 

栈的情况:+

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

此时输出为:a b c * + 

栈的情况为:+(

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

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

栈的情况为:+(

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

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

栈的情况为:+(*

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

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

栈的情况为:+(*

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

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

栈的情况为:+(+

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

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

栈的情况为:+(+

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

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

栈的情况为:+

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

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

栈的情况为:+ * 

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

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

栈的情况为:+ * 

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

此时输出为: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;
}

加载全部内容

相关教程
猜你喜欢
用户评论