表达式求值设计实验报告

课程设计题目：表达式求值

一、问题描述与基本要求

利用栈，实现以下功能：

中缀表达式求值；
中缀表达式转后缀表达式；
后缀表达式求值。

假设用户输入的表达式均合法，且运算符只含+（加号）、-（减号）、*、/、%、(和)，允许浮点数（浮点数计算取模规定为向零取整后得到整数再计算取模）。

二、概要设计

1. 数据结构的设计

我们利用栈来实现上述3个功能。具体原因见后文算法的设计。

2. 算法的设计

2.1 表达式读入与预处理

用户从键盘输入一个语法正确的中缀/后缀表达式，但格式可能并不标准，例如有多余的空格。另外，为了在后面计算表达式编码更方便，我想利用C++中的istringstream，所以要将表达式存储在字符串中，且数与数、数与符号、符号与符号之间都有空格，最后在字符串末尾加上#（原因见下）。

用length表示输入的中缀表达式字符串长度，则

时间复杂度	空间复杂度
$O(length)$	$O(length)$

2.2 计算中缀表达式

先定义运算符的优先级。注意运算符在栈内和栈外的优先级是不同的，这是为了实现同优先级能从左往右计算。

运算符	+ -	* / %	(	)	# ;
isp（栈内优先级）	3	5	1	6	0
icp（栈外优先级）	2	4	6	1	0

定义#或;，是为了后面统一处理表达式求值。

接下来，我们定义两个栈：数值栈（num_stack）和符号栈（sgn_stack）。

从左往右扫描中缀表达式，如果：

遇到数值就直接将它压入数值栈；
遇到运算符（记当前运算符为cur），检查符号栈的栈顶运算符的优先级
1. 栈顶优先级小于cur，则直接压入cur
2. 栈顶优先级大于cur，则弹出栈顶运算符和数值栈的两个数来计算，再把计算结果压入数值栈。重复直到栈顶运算符的优先级不再大于cur，再将cur压入。
3. 栈顶优先级等于cur，从上面的运算符优先级的表格中我们可以知道这时候栈顶是左括号，cur是右括号，那么直接将这两个括号扔掉就好了。
最后数值栈里就只剩下一个数，就是整个中缀表达式的计算结果

如果我们不在原本的中缀表达式后面加#或;，那么还需要把符号栈中的运算符依次弹出来并计算，这无疑让编码更加繁琐更易出错。所以，不如在后面加上#或;，并把优先级设计成最低（0），统一处理。

伪代码如下

for (从左到右扫描中缀表达式)
    if (cur == 数值)
        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，结果存到 c
            num_stack.push(c)
        sgn_stack.push(cur)

用n表示输入的中缀表达式中运算符个数，则

时间复杂度	空间复杂度
$O(n)$	$O(n)$

2.3 中缀表达式转后缀表达式

我们只需要一个符号栈（sgn_stack）就够了。

从左往右扫描中缀表达式，如果：

遇到数值就直接将它输出；
遇到运算符（记当前运算符为cur），检查符号栈的栈顶运算符的优先级
1. 栈顶优先级小于cur，则直接压入cur
2. 栈顶优先级大于cur，则弹出栈顶运算符并输出。重复直到栈顶运算符的优先级不再大于cur，再将cur压入。
3. 栈顶优先级等于cur，从上面的运算符优先级的表格中我们可以知道这时候栈顶是左括号，cur是右括号，那么直接将这两个括号扔掉就好了，因为后缀表达式不需要括号。

同样，这里在原来的中缀表达式后加上#或;会更方便。

后缀表达式并不需要在最后面也加上#或;（因为它的计算和编码已经够简单了）。当然，加上也没问题。

伪代码如下

for (从左到右扫描中缀表达式)
    if (cur == 数值)
        输出 cur
    else // cur == 运算符
        while (isp(sgn_stack.top()) > icp(cur))
            输出 sgn_stack.top() sgn_stack.pop()
        sgn_stack.push(cur)

用length表示输入的中缀表达式字符串长度，则

时间复杂度	空间复杂度
$O(length)$	$O(length)$

2.4 计算后缀表达式

后缀表达式的计算就简单了：遇数压栈，遇符就弹两个数来算。

for (从左到右扫描后缀表达式)
    if (cur == 数值)
        num_stack.push(cur)
    else // cur == 运算符
        b = num_stack.top(), num_stack.pop()
        a = num_stack.top(), num_stack.pop()
        用 cur 计算 a 和 b，结果存到 c
        num_stack.push(c)

用n表示输入的中缀表达式中运算符个数，则

时间复杂度	空间复杂度
$O(n)$	$O(n)$

三、详细设计

1. 每个函数

表达式读入与预处理：详见string _read_expression()；
计算中缀表达式：详见double infix_expression_calc(string infexp)；
中缀表达式转后缀表达式：string infix_expression_to_postfix_expression(string infexp)；
计算后缀表达式double postfix_expression_calc(string posexp = _read_expression())。

2. 设计主函数

主函数主要包括对设计的函数的测试。

四、运行与测试

1. 测试环境

运行环境：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. 在调试程序的过程中遇到的问题与解决方案

暂未发现异常。

3. 设计的测试数据与测试结果

测试1（测试表达式读入与预处理）

样例1

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

测试2（测试计算中缀表达式）

样例2

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

样例3

1.23+4.56

测试3（测试中缀表达式转后缀表达式）

样例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. 程序清单及运行结果

#include "MyStack.h" // 数据结构老师要求自己写栈，用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（符合预期）

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（符合预期）

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

样例3（符合预期）

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

样例4（符合预期）

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（符合预期）

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

样例6（符合预期）

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

样例7（符合预期）

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

五、参考资料

王红梅, 胡明, 王涛. 数据结构(C++版)[M]. 2 版. 清华大学出版社, 2011.
王红梅, 胡明, 王涛. 数据机构(C++版)学习辅导与实验指导[M]. 2 版. 清华大学出版社, 2011.