幽谷奇峰 | 燕雀鸣幽谷，鸿鹄掠奇峰

表达式求值及转换算法

本文是笔者参加网易自虐团，学习《数据结构》课程第二周的成果帖。

后缀表达式求值算法

伪码描述：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
stack operands;   //运算数栈
while (没到表达式尾)
{
    scanf("一个运算对象op");
    if (op is Operand)
        operands.push(op);
    else if (op is Operator)
    {
        operand_right = operands.pop();
        operand_left = operands.pop();
        result = operand_left op operand_right;
        operands.push(result);
    }
    else
    {
        printf("Suffix expression is invalid!");
    }
}
if (operands.size() == 1)
    return operands.top();
else
    printf("Suffix expression is invalid!");

前缀表达式求值算法

算法一：从表达式尾部开始处理(从右至左)

伪码描述：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
stack operands;   //运算数栈
while (没到表达式首)
{
    scanf("一个运算对象op");
    if (op is Operand)
        operands.push(op);
    else if (op is Operator)
    {
        operand_left = operands.pop();
        operand_right = operands.pop();
        result = operand_left op operand_right;
        operands.push(result);
    }
    else
    {
        printf("Prefix expression is invalid!");
    }
}
if (operands.size() == 1)
    return operands.top();
else
    printf("Prefix expression is invalid!");

算法二：从表达式首部开始处理(从左至右)

伪码描述：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
stack operations;  //运算对象栈，元素既可以是运算符，也可以是运算数
while (没到表达式尾)
{
    scanf("一个运算对象op");
    if (op is Operator)
    {
        operations.push(op);
    }
    else if (op is Operand)
    {
        if (operations.top() is Oprerator)
        {
            operations.push(op);
        }
        else
        {
            while(operations.top() is Operand)
            {
                operand_right = op;
                operand_left = operations.pop();
                operator = operations.pop();
                op = operand_left operator operand_right;
            }
            operations.push(op);
        }
    }
    else
    {
        printf("Prefix expression is invalid!");
    }
}
if (operations.size() == 1)
    return operations.top();
else
    printf("Prefix expression is invalid!");

中缀表达式转换为后缀表达式算法

伪码描述：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
stack operators;  //运算符栈
while (没到表达式尾)
{
    scanf("一个运算对象op");
    if (op is Operand)
    {
        printf(op);
    }
    else if (op is Operator)
    {
        if (op 优先级大于 operators.top() && op is not 右括号)
            operators.push(op);
        else if (op is 右括号)
        {
            do
            {
                tmp = operators.pop();
                if (tmp is not 对应左括号)
                {
                    printf(tmp);
                }
                else
                {
                    break;
                }
                if (operators.empty())
                {
                    printf("Infix expression is invalid!");
                }
            }while(1);
        }
        else
        {
            do
            {
                tmp = operators.pop();
                printf(tmp);
            }while(op 优先级小于 operators.top());
            operators.push(op);
        }
    }
    else
    {
        printf("Infix expression is invalid!");
    }
}
while(!operators.empty())
{
    tmp = operators.pop();
    printf(tmp);
}

中缀表达式转换为前缀表达式算法

从表达式尾部开始处理(从右至左)。

伪码描述：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
stack operators;  //运算符栈
stack operations;  //运算对象栈，元素既可以是运算符，也可以是运算数
while (没到表达式首)
{
    scanf("一个运算对象op");
    if (op is Operand)
    {
        operations.push(op);
    }
    else if (op is Operator)
    {
        if (op 优先级大于 operators.top() && op is not 左括号)
            operators.push(op);
        else if (op is 左括号)
        {
            do
            {
                tmp = operators.pop();
                if (tmp is not 对应右括号)
                {
                    operations.push(tmp);
                }
                else
                {
                    break;
                }
                if (operators.empty())
                {
                    printf("Infix expression is invalid!");
                }
            }while(1);
        }
        else
        {
            do
            {
                tmp = operators.pop();
                operations.push(tmp);
            }while(op 优先级小于 operators.top());
            operators.push(op);
        }
    }
    else
    {
        printf("Infix expression is invalid!");
    }
}

while(!operators.empty())
{
    tmp = operators.pop();
    operations.push(tmp);
}

while(!operations.empty())
{
    tmp = operations.pop();
    printf(tmp);
}

运算符优先级表（从上至下优先级依次降低）

适用于中缀转后缀（从左至右）的优先级表：

运算符 说明
栈外：'('
栈外：'['
栈外：'{'
栈外：'^' 幂运算符的结合顺序是从右至左，故栈外优先级高。
栈内：'^'
栈内：'*', '/' 乘除法的结合顺序是从左至右，故栈内优先级高。
栈外：'*', '/'
栈内：'+', '-' 加减法的结合顺序是从左至右，故栈内优先级高。
栈外：'+', '-'
栈内：'(', '[', '{'

适用于中缀转前缀（从右至左）的优先级表：

运算符 说明
栈外：')'
栈外：']'
栈外：'}'
栈内：'^' 幂运算符的结合顺序是从右至左，故栈内优先级高。
栈外：'^'
栈外：'*', '/' 乘除法的结合顺序是从左至右，故栈外优先级高。
栈内：'*', '/'
栈外：'+', '-' 加减法的结合顺序是从左至右，故栈外优先级高。
栈内：'+', '-'
栈内：')', ']', '}'

本作品由 Yysfire 创作，采用知识共享许可协议进行许可。转载时请在显著位置标明本文永久链接：
http://yysfire.github.io/algorithm/algorithm_to_evaluate_and_convert_expression.html

相关文章

最后修改
2014-12-14 20:38
发表时间
2014-12-14 20:04
本文标签
Algorithm 2 后缀表达式 1 前缀表达式 1 RPN 1 数据结构 1 stack 1 中缀表达式 1
关注我
侧栏导航