欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實現(xiàn)中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式詳解

 更新時間:2022年03月22日 09:40:41   作者:玄澈_  
這篇文章主要為大家詳細(xì)介紹了如何利用C++解決實現(xiàn)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的問題,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下

1.題目描述

所謂后綴表達(dá)式是指這樣的一個表達(dá)式:式中不再引用括號,運(yùn)算符號放在兩個運(yùn)算對象之后,所有計算按運(yùn)算符號出現(xiàn)的順序,嚴(yán)格地由左而右進(jìn)行(不用考慮運(yùn)算符的優(yōu)先級)。

如:中綴表達(dá)式 3*(5–2)+7 對應(yīng)的后綴表達(dá)式為:352-*7+ 。

請將給出的中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式并輸出。

2.輸入輸出

輸入樣例: 

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

輸出樣例:

248*+88*1+3/+

3.解題思路

對于中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式,我們需要用以下步驟來解決這個問題:

1.初始化一個個棧:運(yùn)算符棧S1

2.從左往右開始掃描中綴表達(dá)式

I.遇到數(shù)字,直接輸出

II.遇到運(yùn)算符:

  • 若為 '('  直接入棧
  • 若為 ')'  將符號棧中的元素依次出棧并輸出,直到 '(', '(' 只出棧,不輸出
  • 若為其他符號,將符號棧中的元素依次出棧并將其輸出,直到遇到比當(dāng)前符號優(yōu)先級更低的符號或者 '('。將當(dāng)前符號入棧。
  • 掃描完后,將棧中剩余的符號依次輸出。

4.樣例解析 

下面以 a + b * c +(d * e + f) * g 為例子來講講計算機(jī)的轉(zhuǎn)換過程。

1.從左向右開始遍歷表達(dá)式,首先遇到a, 直接將其輸出

此時輸出 :a

棧的情況:空

2.繼續(xù)遍歷表達(dá)式,遇到+,此時??眨瑒t將其放入棧中

此時輸出 :a

棧的情況:+

3.繼續(xù)遍歷表達(dá)式,遇到b,直接將其輸出

此時輸出 :a b

棧的情況:+

4.繼續(xù)遍歷表達(dá)式,遇到*,因為*的優(yōu)先級大于棧頂?shù)?,所以將*入棧

此時輸出 :a b

棧的情況:+*

5.繼續(xù)遍歷表達(dá)式,遇到c,直接將其輸出

此時輸出 :a b c

棧的情況:+*

6.繼續(xù)遍歷表達(dá)式,遇到+, 因為+的優(yōu)先級低于棧頂?shù)?,所以將棧頂?shù)?彈出;然后新的棧頂元素的+與當(dāng)前的+優(yōu)先級相同,所以也要將+彈出;然后??樟?,將現(xiàn)在這個+放入棧中

此時輸出 :a b c * + 

棧的情況:+

7.繼續(xù)遍歷表達(dá)式,遇到(,直接將其放入棧中,不遇到)不會將(彈出。

此時輸出為:a b c * + 

棧的情況為:+(

8.繼續(xù)遍歷表達(dá)式,遇到d,直接將其輸出

此時輸出為:a b c * + d

棧的情況為:+(

9.繼續(xù)遍歷表達(dá)式,遇到*,因為棧頂為(,不遇到)不將(彈出,故直接將*放入棧中。

此時輸出為:a b c * + d

棧的情況為:+(*

10.繼續(xù)遍歷表達(dá)式,遇到e,直接將其輸出

此時輸出為:a b c * + d e

棧的情況為:+(*

11.繼續(xù)遍歷表達(dá)式,遇到+,因為+比棧頂*的優(yōu)先級低,故將*彈出;新的棧頂元素為(,不遇到)不彈出(,故將+放入棧中。

此時輸出為:a b c * + d e *

棧的情況為:+(+

12.繼續(xù)遍歷表達(dá)式,遇到f,直接將其輸出

此時輸出為:a b c * + d e *  f

棧的情況為:+(+

13.繼續(xù)遍歷表達(dá)式,遇到),直接將棧中元素依次彈出并輸出直到遇到(為止,注意:(彈出但不輸出。

此時輸出為:a b c * + d e *  f + 

棧的情況為:+

14.繼續(xù)遍歷表達(dá)式,遇到*,因為*的優(yōu)先級大于棧頂元素+的優(yōu)先級,故直接將*入棧。

此時輸出為:a b c * + d e *  f + 

棧的情況為:+ * 

15.繼續(xù)遍歷表達(dá)式,遇到g,直接將其輸出。

此時輸出為:a b c * + d e *  f + g

棧的情況為:+ * 

16.繼續(xù)遍歷表達(dá)式,為空,遍歷結(jié)束。將棧內(nèi)元素依次彈出。

此時輸出為:a b c * + d e *  f + g * +

棧的情況為:空

至此,中綴表達(dá)式轉(zhuǎn)后綴已經(jīng)全部完成,結(jié)果為 a b c * + d e *  f + g * +

5.代碼實現(xiàn)

5.1.優(yōu)先級確認(rèn)

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

5.2.轉(zhuǎn)換函數(shù)

//引用符號提高轉(zhuǎn)換效率
void Trans(string &str, string &str1)
{
    stack<char> s;
    int i;
    for(i = 0; i < str.size(); i ++ )
    {
        //是數(shù)字的情況下直接輸出
        if(str[i] >= '0' && str[i] <= '9' || str[i] >= 'a' && str[i] <= 'z')
        {
            str1 += str[i];
        }
        else //不是數(shù)字的情況分類討論進(jìn)行判斷
        {
            //棧為空時直接入棧
            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 
            {
                //棧頂元素的優(yōu)先級大于等于當(dāng)前的運(yùn)算符,就將其輸出
                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;
}
 
//引用符號提高轉(zhuǎn)換效率
void Trans(string &str, string &str1)
{
    stack<char> s;
    int i;
    for(i = 0; i < str.size(); i ++ )
    {
        //是數(shù)字的情況下直接輸出
        if(str[i] >= '0' && str[i] <= '9' || str[i] >= 'a' && str[i] <= 'z')
        {
            str1 += str[i];
        }
        else //不是數(shù)字的情況分類討論進(jìn)行判斷
        {
            //棧為空時直接入棧
            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 
            {
                //棧頂元素的優(yōu)先級大于等于當(dāng)前的運(yùn)算符,就將其輸出
                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()
{
    //輸入前綴表達(dá)式
    string infix;
    string postfix;
    cin >> infix;
    
    Trans(infix, postfix);
    
    cout << postfix << endl;
    return 0;
}

以上就是C++實現(xiàn)中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式詳解的詳細(xì)內(nèi)容,更多關(guān)于C++中綴轉(zhuǎn)后綴表達(dá)式的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • C++函數(shù)重載的定義與原因詳解

    C++函數(shù)重載的定義與原因詳解

    這篇文章主要為大家詳細(xì)介紹了Python實現(xiàn)學(xué)生成績管理系統(tǒng),使用數(shù)據(jù)庫,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • c++ 數(shù)組定義及初始化詳解

    c++ 數(shù)組定義及初始化詳解

    這篇文章主要介紹了c++ 數(shù)組定義及初始化詳解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-12-12
  • C語言return知識點總結(jié)

    C語言return知識點總結(jié)

    在本篇文章里小編給大家整理的是關(guān)于C語言return知識點總結(jié)內(nèi)容,需要的朋友們可以學(xué)習(xí)參考下。
    2020-02-02
  • C語言實現(xiàn)哈夫曼樹

    C語言實現(xiàn)哈夫曼樹

    這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)哈夫曼樹,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-04-04
  • 基于C++的攝像頭圖像采集及拼接程序的簡單實現(xiàn)

    基于C++的攝像頭圖像采集及拼接程序的簡單實現(xiàn)

    本程序是在?ubuntu14.04?平臺下實現(xiàn)的,在本項目目錄下,已經(jīng)有編譯生成的可執(zhí)行程序,其中Camera_to_Frmae.cpp是我們從雙攝像頭實時抓取單幀圖像的源碼,對基于C++的攝像頭圖像采集及拼接程序的實現(xiàn)感興趣的朋友一起看看吧
    2022-01-01
  • C++實現(xiàn)二分法的一些細(xì)節(jié)(常用場景)

    C++實現(xiàn)二分法的一些細(xì)節(jié)(常用場景)

    二分法算法思想首先確定有根區(qū)間,將區(qū)間二等分,通過判斷f(x)的符號,逐步將有根區(qū)間縮小,直至有根區(qū)間足夠小,便可求出滿足精度要求的近似值
    2021-07-07
  • Qt?TCP網(wǎng)絡(luò)通信學(xué)習(xí)

    Qt?TCP網(wǎng)絡(luò)通信學(xué)習(xí)

    用于數(shù)據(jù)傳輸?shù)牡蛯泳W(wǎng)絡(luò)協(xié)議,多個物聯(lián)網(wǎng)協(xié)議都是基于TCP協(xié)議的,這篇文章為大家介紹了Qt?TCP網(wǎng)絡(luò)通信,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-08-08
  • Visual?Studio?2022?激活碼(親測可用)

    Visual?Studio?2022?激活碼(親測可用)

    在?Visual?Studio?2019?的基礎(chǔ)上,新版集成開發(fā)壞境提供了非常多的改進(jìn),包括對?64?位、.NET?6?的支持,為核心調(diào)試器提供更好的性能。本文給大家分享Visual?Studio?2022?激活碼,需要的朋友參考下吧
    2021-12-12
  • C++ 詳細(xì)講解對象的構(gòu)造順序

    C++ 詳細(xì)講解對象的構(gòu)造順序

    對象的構(gòu)造往往和構(gòu)造函數(shù)會牽扯在一起,構(gòu)造函數(shù)的函數(shù)可能會由非常復(fù)雜的邏輯所組成,不同類的構(gòu)造函數(shù)的程序邏輯很可能是相互依賴的,當(dāng)這種相互依賴一旦成立,那么對象的構(gòu)造順序很可能導(dǎo)致難以調(diào)試的Bug出現(xiàn)
    2022-04-04
  • C++實現(xiàn)圖書館案例

    C++實現(xiàn)圖書館案例

    這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)圖書館案例,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-06-06

最新評論