課程設(shè)計(jì)題目：表達(dá)式求值
一、問(wèn)題描述與基本要求
利用棧穗慕，實(shí)現(xiàn)以下功能：
- 中綴表達(dá)式求值饿敲；
- 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式；
- 后綴表達(dá)式求值逛绵。
假設(shè)用戶輸入的表達(dá)式均合法怀各，且運(yùn)算符只含+（加號(hào)）、-（減號(hào)）术浪、*瓢对、/、%胰苏、(和)硕蛹，允許浮點(diǎn)數(shù)（浮點(diǎn)數(shù)計(jì)算取模規(guī)定為向零取整后得到整數(shù)再計(jì)算取模）。
二硕并、概要設(shè)計(jì)
1. 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)
我們利用棧來(lái)實(shí)現(xiàn)上述3個(gè)功能法焰。具體原因見(jiàn)后文算法的設(shè)計(jì)。
2. 算法的設(shè)計(jì)
2.1 表達(dá)式讀入與預(yù)處理
用戶從鍵盤(pán)輸入一個(gè)語(yǔ)法正確的中綴/后綴表達(dá)式倔毙，但格式可能并不標(biāo)準(zhǔn)埃仪，例如有多余的空格。另外陕赃，為了在后面計(jì)算表達(dá)式編碼更方便卵蛉，我想利用C++中的istringstream，所以要將表達(dá)式存儲(chǔ)在字符串中么库，且數(shù)與數(shù)傻丝、數(shù)與符號(hào)、符號(hào)與符號(hào)之間都有空格廊散，最后在字符串末尾加上#（原因見(jiàn)下）桑滩。
用length表示輸入的中綴表達(dá)式字符串長(zhǎng)度，則
| 時(shí)間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|
2.2 計(jì)算中綴表達(dá)式
先定義運(yùn)算符的優(yōu)先級(jí)允睹。注意運(yùn)算符在棧內(nèi)和棧外的優(yōu)先級(jí)是不同的运准，這是為了實(shí)現(xiàn)同優(yōu)先級(jí)能從左往右計(jì)算。
| 運(yùn)算符 | + - | * / % | ( | ) | # ; |
|---|---|---|---|---|---|
| isp（棧內(nèi)優(yōu)先級(jí)） | 3 | 5 | 1 | 6 | 0 |
| icp（棧外優(yōu)先級(jí)） | 2 | 4 | 6 | 1 | 0 |
定義#或;缭受，是為了后面統(tǒng)一處理表達(dá)式求值胁澳。
接下來(lái)，我們定義兩個(gè)棧：數(shù)值棧（num_stack）和符號(hào)棧（sgn_stack）米者。
從左往右掃描中綴表達(dá)式韭畸，如果：
- 遇到數(shù)值就直接將它壓入數(shù)值棧宇智；
- 遇到運(yùn)算符（記當(dāng)前運(yùn)算符為cur），檢查符號(hào)棧的棧頂運(yùn)算符的優(yōu)先級(jí)
- 棧頂優(yōu)先級(jí)小于cur胰丁，則直接壓入cur
- 棧頂優(yōu)先級(jí)大于cur随橘，則彈出棧頂運(yùn)算符和數(shù)值棧的兩個(gè)數(shù)來(lái)計(jì)算，再把計(jì)算結(jié)果壓入數(shù)值棧锦庸。重復(fù)直到棧頂運(yùn)算符的優(yōu)先級(jí)不再大于cur机蔗，再將cur壓入。
- 棧頂優(yōu)先級(jí)等于cur甘萧，從上面的運(yùn)算符優(yōu)先級(jí)的表格中我們可以知道這時(shí)候棧頂是左括號(hào)萝嘁，cur是右括號(hào)，那么直接將這兩個(gè)括號(hào)扔掉就好了扬卷。
- 最后數(shù)值棧里就只剩下一個(gè)數(shù)牙言，就是整個(gè)中綴表達(dá)式的計(jì)算結(jié)果
如果我們不在原本的中綴表達(dá)式后面加#或;，那么還需要把符號(hào)棧中的運(yùn)算符依次彈出來(lái)并計(jì)算怪得，這無(wú)疑讓編碼更加繁瑣更易出錯(cuò)咱枉。所以，不如在后面加上#或;徒恋，并把優(yōu)先級(jí)設(shè)計(jì)成最低（0）庞钢，統(tǒng)一處理。
偽代碼如下
for (從左到右掃描中綴表達(dá)式)
if (cur == 數(shù)值)
num_stack.push(cur)
else // cur == 運(yùn)算符
while (isp(sgn_stack.top()) > icp(cur))
b = num_stack.top(), num_stack.pop()
a = num_stack.top(), num_stack.pop()
用 sgn_stack.top() 計(jì)算 a 和 b因谎，結(jié)果存到 c
num_stack.push(c)
sgn_stack.push(cur)
用n表示輸入的中綴表達(dá)式中運(yùn)算符個(gè)數(shù)，則
| 時(shí)間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|
2.3 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
我們只需要一個(gè)符號(hào)棧（sgn_stack）就夠了颜懊。
從左往右掃描中綴表達(dá)式财岔，如果：
- 遇到數(shù)值就直接將它輸出；
- 遇到運(yùn)算符（記當(dāng)前運(yùn)算符為cur）河爹，檢查符號(hào)棧的棧頂運(yùn)算符的優(yōu)先級(jí)
- 棧頂優(yōu)先級(jí)小于cur匠璧，則直接壓入cur
- 棧頂優(yōu)先級(jí)大于cur，則彈出棧頂運(yùn)算符并輸出咸这。重復(fù)直到棧頂運(yùn)算符的優(yōu)先級(jí)不再大于cur夷恍，再將cur壓入。
- 棧頂優(yōu)先級(jí)等于cur媳维，從上面的運(yùn)算符優(yōu)先級(jí)的表格中我們可以知道這時(shí)候棧頂是左括號(hào)酿雪，cur是右括號(hào)，那么直接將這兩個(gè)括號(hào)扔掉就好了侄刽，因?yàn)楹缶Y表達(dá)式不需要括號(hào)指黎。
同樣，這里在原來(lái)的中綴表達(dá)式后加上#或;會(huì)更方便州丹。
后綴表達(dá)式并不需要在最后面也加上#或;（因?yàn)樗挠?jì)算和編碼已經(jīng)夠簡(jiǎn)單了）醋安。當(dāng)然杂彭，加上也沒(méi)問(wèn)題。
偽代碼如下
for (從左到右掃描中綴表達(dá)式)
if (cur == 數(shù)值)
輸出 cur
else // cur == 運(yùn)算符
while (isp(sgn_stack.top()) > icp(cur))
輸出 sgn_stack.top() sgn_stack.pop()
sgn_stack.push(cur)
用length表示輸入的中綴表達(dá)式字符串長(zhǎng)度吓揪，則
| 時(shí)間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|
2.4 計(jì)算后綴表達(dá)式
后綴表達(dá)式的計(jì)算就簡(jiǎn)單了：遇數(shù)壓棧亲怠，遇符就彈兩個(gè)數(shù)來(lái)算。
for (從左到右掃描后綴表達(dá)式)
if (cur == 數(shù)值)
num_stack.push(cur)
else // cur == 運(yùn)算符
b = num_stack.top(), num_stack.pop()
a = num_stack.top(), num_stack.pop()
用 cur 計(jì)算 a 和 b柠辞，結(jié)果存到 c
num_stack.push(c)
用n表示輸入的中綴表達(dá)式中運(yùn)算符個(gè)數(shù)团秽，則
| 時(shí)間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|
三、詳細(xì)設(shè)計(jì)
1. 每個(gè)函數(shù)
- 表達(dá)式讀入與預(yù)處理：詳見(jiàn)
string _read_expression()钾腺； - 計(jì)算中綴表達(dá)式：詳見(jiàn)
double infix_expression_calc(string infexp)徙垫； - 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式：
string infix_expression_to_postfix_expression(string infexp)； - 計(jì)算后綴表達(dá)式
double postfix_expression_calc(string posexp = _read_expression())放棒。
2. 設(shè)計(jì)主函數(shù)
主函數(shù)主要包括對(duì)設(shè)計(jì)的函數(shù)的測(cè)試姻报。
四、運(yùn)行與測(cè)試
1. 測(cè)試環(huán)境
運(yù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
運(yùn)行終端：cmd
2. 在調(diào)試程序的過(guò)程中遇到的問(wèn)題與解決方案
暫未發(fā)現(xiàn)異常间螟。
3. 設(shè)計(jì)的測(cè)試數(shù)據(jù)與測(cè)試結(jié)果
測(cè)試1（測(cè)試表達(dá)式讀入與預(yù)處理）
樣例1
1+2 * ( 3 - (4-5) /6 )
測(cè)試2（測(cè)試計(jì)算中綴表達(dá)式）
樣例2
1+2*(3-(4-5)/6)
樣例3
1.23+4.56
測(cè)試3（測(cè)試中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式）
樣例4
1+2*(3-(4-5)/6)
樣例5
1.23+4.56
測(cè)試4（測(cè)試計(jì)算后綴表達(dá)式）
樣例6
1 2 3 4 5 - 6 / - * +
樣例7
1.23 4.56 +
4. 程序清單及運(yùn)行結(jié)果
#include "MyStack.h" // 數(shù)據(jù)結(jié)構(gòu)老師要求自己寫(xiě)棧吴旋，用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
五、參考資料
- 王紅梅, 胡明, 王濤. 數(shù)據(jù)結(jié)構(gòu)(C++版)[M]. 2 版. 清華大學(xué)出版社, 2011.
- 王紅梅, 胡明, 王濤. 數(shù)據(jù)機(jī)構(gòu)(C++版)學(xué)習(xí)輔導(dǎo)與實(shí)驗(yàn)指導(dǎo)[M]. 2 版. 清華大學(xué)出版社, 2011.
