中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

C++如何實現中綴表達式轉化為后綴表達式

發布時間:2022-03-22 11:05:11 來源:億速云 閱讀:306 作者:小新 欄目:開發技術

這篇文章將為大家詳細講解有關C++如何實現中綴表達式轉化為后綴表達式,小編覺得挺實用的,因此分享給大家做個參考,希望大家閱讀完這篇文章后可以有所收獲。

1.題目描述

C++如何實現中綴表達式轉化為后綴表達式

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

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

請將給出的中綴表達式轉化為后綴表達式并輸出。

2.輸入輸出

C++如何實現中綴表達式轉化為后綴表達式

輸入樣例: 

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.優先級確認

C++如何實現中綴表達式轉化為后綴表達式

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++如何實現中綴表達式轉化為后綴表達式”這篇文章就分享到這里了,希望以上內容可以對大家有一定的幫助,使各位可以學到更多知識,如果覺得文章不錯,請把它分享出去讓更多的人看到。

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

c++
AI

广宁县| 梓潼县| 德清县| 柞水县| 左权县| 上高县| 巴南区| 宁陵县| 奉化市| 呼玛县| 白朗县| 贵阳市| 柘城县| 伊金霍洛旗| 博湖县| 黄石市| 根河市| 桑植县| 大兴区| 西平县| 察隅县| 新疆| 枝江市| 泸西县| 平潭县| 五家渠市| 陆河县| 兴仁县| 施甸县| 霍城县| 门头沟区| 神池县| 调兵山市| 龙南县| 双鸭山市| 开化县| 宁国市| 抚顺市| 广平县| 普宁市| 宣化县|