数据结构——中缀表达式

发表于 更新于 分类于 ， 阅读次数：

数据结构——中缀表达式

利用中缀表达式直接求值

要实现中缀表达式直接求值，必须设置两个栈，一个栈用于存放操作数，记作 OPND； 另一个栈用于存放操作符，记作 OPTR。

中缀表达式求值算法步骤如下：

  1. 初始化：操作符栈中放置一个元素 @。
  2. 依次读取中缀表达式中的每一个字符，对于不同类型的字符按以下情况处理：
    1. 若读到的是操作数，则压入操作数栈，并读取下一个字符。
    2. 若读到的是操作符 c，则将操作符栈的栈顶元素 pre_op与之进行比较，会出现以下 3 种情况：
      • 若 pre_op < c，则将 c 入栈，并读取下一个字符。
      • 若 pre_op = c，则将 pre_op 出栈，并读取下一个字符。
      • 若 pre_op > c，则将 pre_op 出栈，并在操作数栈中退栈 2 次，依次得到操作数 b 和 a，然后进行 a pre_op b 运算，将运算结果压入操作数栈。
  3. 扫描完毕时，操作数栈中只有一个元素，即计算结果。
IMG_20241026_164151 
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
//中缀表达式，实数
double Expression_Eval2()
{
	SeqStack<char, 100> OPTR;
	SeqStack<double, 100> OPND;
	OPTR.Push('@');
	char ch = getchar();
	while (ch != '@' || OPTR.Top() != '@')
	{
		if (isdigit(ch) || ch == '.')
		{
			// 处理多位数和小数
			string number;
			while (isdigit(ch) || ch == '.')
			{
				number += ch;
				ch = getchar();
			}
			OPND.Push(stod(number));
		}
		else
		{
			char pre_op = OPTR.Top();
			switch (Precede(pre_op, ch))
			{
			case '<':
				OPTR.Push(ch);
				ch = getchar();
				break;
			case '=':
				OPTR.Pop();
				ch = getchar();
				break;
			case '>':
				char pre_op = OPTR.Pop();
				double b = OPND.Pop();
				double a = OPND.Pop();
				OPND.Push(Operate(a, pre_op, b));
				break;
			
			}
		}
	}
	return OPND.Top();
}

Precede(pre_op, ch)为进行算符优先级比较的函数

Operate(a, pre_op, b)为计算函数

利用后缀表达式求值

优点

后缀是指把操作符放在两个操作数的后面。采用后缀表示的算术表达式被称为后缀表达式或后缀算。 在后缀表达式中，完全按照操作符出现的先后顺序进行计算过程，不存在括号，也不存在优先级的差别。

将中缀表达式转换成等价的后缀表达式求值时，不需要再考虑操作符的优先级，只需从左到右扫描一边后缀表达式即可。只需设置一个OPND栈用于存放操作数

先将中缀表达式转成后缀表达式

把中缀表达式转换为后缀表达式算法的基本思路如下：

  1. 初始化：操作符栈中放置一个元素 @。

  2. 依次读入中缀表达式中的每个字符

    ，对于不同类型的字符按不同情况进行处理：

    1. 若读到的是操作数，则输出该操作数，并读取下一个字符。
    2. 若读到的是左括号 (，则把它压入 OPTR 栈中，并读取下一个字符。
    3. 若读到的是右括号 )，则表明括号内的中缀表达式已经扫描完毕，将 OPTR 栈从栈顶直到左括号之前的操作符依次出栈并输出，然后将左括号出栈，并读取下一个字符。
    4. 若读到的是操作符 c，则将操作符栈的栈顶元素 pre_op与之进行比较：
      • 若 pre_op < c，则将 c 入栈，并读取下一个字符。
      • 若 pre_op >= c，则将 pre_op 出栈并输出。
    5. 若读到的是结束符 @，则把栈中剩余的操作符依次出栈并输出，即可得到转换成的后缀表达式。

后缀表达式求值

后缀表达式求值算法的基本思路如下

  1. 依次读入后缀表达式中的每个字符

    ，直至表达式结束。

    • 若读到的是操作数，则入 OPND 栈。
    • 若读到的是操作符，则在 OPND 栈中退栈两个元素（先退出的是操作符右侧，后退出的是操作符左侧），然后用该操作符进行运算，并将运算结果压入 OPND 栈中。

  2. 后缀表达式扫描完毕时，若 OPND 栈中仅有一个元素，即为运算结果。