表達式求值設(shè)計實驗報告

課程設(shè)計題目：表達式求值

一、問題描述與基本要求

利用棧，實現(xiàn)以下功能：

  1. 中綴表達式求值；
  2. 中綴表達式轉(zhuǎn)后綴表達式；
  3. 后綴表達式求值。

假設(shè)用戶輸入的表達式均合法，且運算符只含+（加號）、-（減號）、*、/、%、(和)，允許浮點數(shù)（浮點數(shù)計算取模規(guī)定為向零取整后得到整數(shù)再計算取模）。

二、概要設(shè)計

1. 數(shù)據(jù)結(jié)構(gòu)的設(shè)計

我們利用棧來實現(xiàn)上述3個功能。具體原因見后文算法的設(shè)計。

2. 算法的設(shè)計

2.1 表達式讀入與預(yù)處理

用戶從鍵盤輸入一個語法正確的中綴/后綴表達式，但格式可能并不標(biāo)準，例如有多余的空格。另外，為了在后面計算表達式編碼更方便，我想利用C++中的istringstream，所以要將表達式存儲在字符串中，且數(shù)與數(shù)、數(shù)與符號、符號與符號之間都有空格，最后在字符串末尾加上#（原因見下）。

用length表示輸入的中綴表達式字符串長度，則

時間復(fù)雜度 空間復(fù)雜度
O(length) O(length)

2.2 計算中綴表達式

先定義運算符的優(yōu)先級。注意運算符在棧內(nèi)和棧外的優(yōu)先級是不同的，這是為了實現(xiàn)同優(yōu)先級能從左往右計算。

運算符 + - * / % ( ) # ;
isp（棧內(nèi)優(yōu)先級） 3 5 1 6 0
icp（棧外優(yōu)先級） 2 4 6 1 0

定義#或;，是為了后面統(tǒng)一處理表達式求值。

接下來，我們定義兩個棧：數(shù)值棧（num_stack）和符號棧（sgn_stack）。

從左往右掃描中綴表達式，如果：

  1. 遇到數(shù)值就直接將它壓入數(shù)值棧；
  2. 遇到運算符（記當(dāng)前運算符為cur），檢查符號棧的棧頂運算符的優(yōu)先級
    1. 棧頂優(yōu)先級小于cur，則直接壓入cur
    2. 棧頂優(yōu)先級大于cur，則彈出棧頂運算符和數(shù)值棧的兩個數(shù)來計算，再把計算結(jié)果壓入數(shù)值棧。重復(fù)直到棧頂運算符的優(yōu)先級不再大于cur，再將cur壓入。
    3. 棧頂優(yōu)先級等于cur，從上面的運算符優(yōu)先級的表格中我們可以知道這時候棧頂是左括號，cur是右括號，那么直接將這兩個括號扔掉就好了。
  3. 最后數(shù)值棧里就只剩下一個數(shù)，就是整個中綴表達式的計算結(jié)果

如果我們不在原本的中綴表達式后面加#或;，那么還需要把符號棧中的運算符依次彈出來并計算，這無疑讓編碼更加繁瑣更易出錯。所以，不如在后面加上#或;，并把優(yōu)先級設(shè)計成最低（0），統(tǒng)一處理。

偽代碼如下

for (從左到右掃描中綴表達式)
    if (cur == 數(shù)值)
        num_stack.push(cur)
    else // cur == 運算符
        while (isp(sgn_stack.top()) > icp(cur))
            b = num_stack.top(), num_stack.pop()
            a = num_stack.top(), num_stack.pop()
            用 sgn_stack.top() 計算 a 和 b，結(jié)果存到 c
            num_stack.push(c)
        sgn_stack.push(cur)

用n表示輸入的中綴表達式中運算符個數(shù)，則

時間復(fù)雜度 空間復(fù)雜度
O(n) O(n)

2.3 中綴表達式轉(zhuǎn)后綴表達式

我們只需要一個符號棧（sgn_stack）就夠了。

從左往右掃描中綴表達式，如果：

  1. 遇到數(shù)值就直接將它輸出；
  2. 遇到運算符（記當(dāng)前運算符為cur），檢查符號棧的棧頂運算符的優(yōu)先級
    1. 棧頂優(yōu)先級小于cur，則直接壓入cur
    2. 棧頂優(yōu)先級大于cur，則彈出棧頂運算符并輸出。重復(fù)直到棧頂運算符的優(yōu)先級不再大于cur，再將cur壓入。
    3. 棧頂優(yōu)先級等于cur，從上面的運算符優(yōu)先級的表格中我們可以知道這時候棧頂是左括號，cur是右括號，那么直接將這兩個括號扔掉就好了，因為后綴表達式不需要括號。

同樣，這里在原來的中綴表達式后加上#或;會更方便。

后綴表達式并不需要在最后面也加上#或;（因為它的計算和編碼已經(jīng)夠簡單了）。當(dāng)然，加上也沒問題。

偽代碼如下

for (從左到右掃描中綴表達式)
    if (cur == 數(shù)值)
        輸出 cur
    else // cur == 運算符
        while (isp(sgn_stack.top()) > icp(cur))
            輸出 sgn_stack.top() sgn_stack.pop()
        sgn_stack.push(cur)

用length表示輸入的中綴表達式字符串長度，則

時間復(fù)雜度 空間復(fù)雜度
O(length) O(length)

2.4 計算后綴表達式

后綴表達式的計算就簡單了：遇數(shù)壓棧，遇符就彈兩個數(shù)來算。

for (從左到右掃描后綴表達式)
    if (cur == 數(shù)值)
        num_stack.push(cur)
    else // cur == 運算符
        b = num_stack.top(), num_stack.pop()
        a = num_stack.top(), num_stack.pop()
        用 cur 計算 a 和 b，結(jié)果存到 c
        num_stack.push(c)

用n表示輸入的中綴表達式中運算符個數(shù)，則

時間復(fù)雜度 空間復(fù)雜度
O(n) O(n)

三、詳細設(shè)計

1. 每個函數(shù)

  1. 表達式讀入與預(yù)處理：詳見string _read_expression()；
  2. 計算中綴表達式：詳見double infix_expression_calc(string infexp)；
  3. 中綴表達式轉(zhuǎn)后綴表達式：string infix_expression_to_postfix_expression(string infexp)；
  4. 計算后綴表達式double postfix_expression_calc(string posexp = _read_expression())。

2. 設(shè)計主函數(shù)

主函數(shù)主要包括對設(shè)計的函數(shù)的測試。

四、運行與測試

1. 測試環(huán)境

運行環(huán)境：Windows 20H2, i7-9750H @ 2.60GHz, 16GB RAM

編譯器：g++ (gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project))

編譯命令：-g

運行終端：cmd

2. 在調(diào)試程序的過程中遇到的問題與解決方案

暫未發(fā)現(xiàn)異常。

3. 設(shè)計的測試數(shù)據(jù)與測試結(jié)果

測試1（測試表達式讀入與預(yù)處理）

樣例1

     1+2   * (  3 -  (4-5)    /6  )

測試2（測試計算中綴表達式）

樣例2

1+2*(3-(4-5)/6)

樣例3

1.23+4.56

測試3（測試中綴表達式轉(zhuǎn)后綴表達式）

樣例4

1+2*(3-(4-5)/6)

樣例5

1.23+4.56

測試4（測試計算后綴表達式）

樣例6

1 2 3 4 5 - 6 / - * +

樣例7

1.23 4.56 +

4. 程序清單及運行結(jié)果

#include "MyStack.h" // 數(shù)據(jù)結(jié)構(gòu)老師要求自己寫棧，用STL的stack也可
#include <cstring>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

string _read_expression();
double infix_expression_calc(string infexp = _read_expression());
string infix_expression_to_postfix_expression(string infexp = _read_expression());
double postfix_expression_calc(string posexp = _read_expression());

int main()
{
    /* test read */
    // istringstream iss(_read_expression());
    // cout << "length: " << iss.str().length() << "\n";
    // char s[20];
    // while (iss >> s) cout << s << "\n";

    /* test infix_expression_calc */
    // cout << infix_expression_calc(_read_expression());

    /* test infexp to posexp */
    // cout << infix_expression_to_postfix_expression();

    /* test postfix_expression_calc */
    // cout << postfix_expression_calc(_read_expression());

    return 0;
}

inline int _check_ch_type(const char &ch)
{
    if (ch >= '0' && ch <= '9' || ch == '.') return 1; // number
    if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '%' ||
        ch == '(' || ch == ')')
        return 2;            // sign
    if (ch == ' ') return 0; // space
    return -1;               // illegal character
}

string _read_expression()
{
    string src; getline(cin, src);
    int pre = 0;
    vector<char> exp;
    for (int i = 0; i < src.length(); i++)
    {
        int chk = _check_ch_type(src[i]);
        if (chk == -1) throw "illegal expression";
        if (chk == 0 && exp.back() == ' ') continue;
        if (pre * chk >= 2) exp.push_back(' ');
        exp.push_back(src[i]);
        pre = chk;
    }
    exp.push_back(' '); exp.push_back('#'); exp.push_back('\0');
    return string(exp.begin(), exp.end());
}

double _string_to_double(char *s)
{
    int cnt = -100000000;
    int len = strlen(s);
    double x = 0;
    for (int i = 0; i < len; i++, cnt++)
        if (s[i] == '.') cnt = -1;
        else x = x * 10 + s[i] - '0';
    double t = 1;
    while (cnt-- > 0) t *= 10;
    return x / t;
}

int _get_isp(char ch)
{
    if (ch == '+' || ch == '-') return 3;
    if (ch == '*' || ch == '/' || ch == '%') return 5;
    if (ch == '(') return 1;
    if (ch == ')') return 6;
    if (ch == '#' || ch == ';') return 0;
    return -1;
}
int _get_icp(char ch)
{
    if (ch == '+' || ch == '-') return 2;
    if (ch == '*' || ch == '/' || ch == '%') return 4;
    if (ch == '(') return 6;
    if (ch == ')') return 1;
    if (ch == '#' || ch == ';') return 0;
    return -1;
}

double _calc(double a, char sgn, double b)
{
    switch (sgn)
    {
    case '+': return a + b;
    case '-': return a - b;
    case '*': return a * b;
    case '/': return a / b;
    case '%': return (long long)a % (long long)b;
    default: throw "illegal sign";
    }
}

double infix_expression_calc(string infexp)
{
    istringstream is(infexp);
    Stack<double> num_stack;
    Stack<char> sgn_stack;
    char res[20];
    while (is >> res)
    {
        if (res[0] >= '0' && res[0] <= '9')
            num_stack.push(_string_to_double(res));
        else
        {
            int _icp = _get_icp(res[0]);
            while (!sgn_stack.empty() && _get_isp(sgn_stack.top()) > _icp)
            {
                double b = num_stack.top(); num_stack.pop();
                double a = num_stack.top(); num_stack.pop();
                num_stack.push(_calc(a, sgn_stack.top(), b));
                sgn_stack.pop();
            }
            if (!sgn_stack.empty() && _get_isp(sgn_stack.top()) == _icp)
            {
                sgn_stack.pop();
                continue;
            }
            sgn_stack.push(res[0]);
        }
    }
    return num_stack.top();
}

string infix_expression_to_postfix_expression(string infexp)
{
    vector<char> posexp;
    Stack<char> sgn_stack;
    char buffer[20]; int bufcnt = 0;
    for (int i = 0; i < infexp.length(); i++)
    {
        char &cur = infexp[i];
        if (cur == ' ')
        {
            if (bufcnt)
            {
                for (int j = 0; j < bufcnt; j++) posexp.push_back(buffer[j]);
                posexp.push_back(' ');
                bufcnt = 0;
            }
            continue;
        }
        if (cur >= '0' && cur <= '9' || cur == '.') 
            buffer[bufcnt++] = cur;
        else
        {
            int _icp = _get_icp(cur);
            while (!sgn_stack.empty() && _get_isp(sgn_stack.top()) > _icp)
            {
                posexp.push_back(sgn_stack.top());
                posexp.push_back(' ');
                sgn_stack.pop();
            }
            if (!sgn_stack.empty() && _get_isp(sgn_stack.top()) == _icp)
            {
                sgn_stack.pop();
                continue;
            }
            sgn_stack.push(cur);
        }
    }
    posexp.push_back('#'); posexp.push_back('\0');
    return string(posexp.begin(), posexp.end());
}

double postfix_expression_calc(string posexp)
{
    istringstream is(posexp);
    Stack<double> num_stack;
    char res[20];
    while (is >> res)
    {
        if (_check_ch_type(res[0]) < 0) break;
        if (res[0] >= '0' && res[0] <= '9')
            num_stack.push(_string_to_double(res));
        else
        {
            double b = num_stack.top(); num_stack.pop();
            double a = num_stack.top(); num_stack.pop();
            num_stack.push(_calc(a, res[0], b));
        }
    }
    return num_stack.top();
}

// MyStack.h

template <typename T>
struct Node {
    T data;
    Node *next;
};

template <typename T>
class Stack {
public:
    Stack() {}
    ~Stack() { for (Node<T> *tmp; _top != nullptr;) { tmp = _top; _top = _top->next; delete tmp; } }
    void push(T x) { _top = new Node<T>{x, _top}; }
    void pop() { Node<T> *tmp = _top; _top = _top->next; delete tmp; }
    T top() { return _top->data; }
    bool empty() { return _top == nullptr; }

private:
    Node<T> *_top = nullptr;
};

樣例1（符合預(yù)期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week07\ex3>main
1+2   * (  3 -  (4-5)    /6  )
length: 31
1
+
2
*
(
3
-
(
4
-
5
)
/
6
)
#

樣例2（符合預(yù)期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week07\ex3>main
1+2*(3-(4-5)/6)
7.33333

樣例3（符合預(yù)期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week07\ex3>main
1.23+4.56
5.79

樣例4（符合預(yù)期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week07\ex3>main
1+2*(3-(4-5)/6)
1 2 3 4 5 - 6 / - * + #

樣例5（符合預(yù)期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week07\ex3>main
1.23+4.56
1.23 4.56 + #

樣例6（符合預(yù)期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week07\ex3>main
1 2 3 4 5 - 6 / - * +
7.33333

樣例7（符合預(yù)期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week07\ex3>main
1.23 4.56 +
5.79

五、參考資料

  1. 王紅梅, 胡明, 王濤. 數(shù)據(jù)結(jié)構(gòu)(C++版)[M]. 2 版. 清華大學(xué)出版社, 2011.
  2. 王紅梅, 胡明, 王濤. 數(shù)據(jù)機構(gòu)(C++版)學(xué)習(xí)輔導(dǎo)與實驗指導(dǎo)[M]. 2 版. 清華大學(xué)出版社, 2011.
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容