逆波兰表达式

发表于   |   分类于   |  

逆波兰表达式求值

逆波兰表达式也叫后缀表达式，其求值过程可以用到栈来辅助存储。假定待求值的后缀表达式为：6 5 2 3 + 8 * + 3 + *，则其求值过程如下：
1）遍历表达式，遇到的数字首先放入栈中，此时栈如下所示：
1
2）接着读到“+”，则弹出3和2，执行3+2，计算结果等于5，并将5压入到栈中。
2
3）读到8，将其直接放入栈中。
3
4）读到“*”，弹出8和5，执行8*5，并将结果40压入栈中。而后过程类似，读到“+”，将40和5弹出，将40+5的结果45压入栈…以此类推。最后求的值288。

逆波兰表达式的计算方法

-若当前字符是操作数，则入栈
-若当前字符为操作符，则弹出栈中两个操作数，计算后压栈
-若某次操作，栈内无法弹出两个操作数，则表达式有误

中缀表达式转后缀表达式

-如果遇到操作数，我们就直接将其输出。
-如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
-如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
-如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到” ) “的情况下我们才弹出” ( “，其他情况我们都不会弹出” ( “。
-如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

例子

规则很多，还是用实例比较容易说清楚整个过程。以上面的转换为例，输入为a + b * c + (d * e + f)*g，处理过程如下：

  1. 首先读到a，直接输出。
  2. 读到“+”，将其放入到栈中。
  3. 读到b，直接输出。
    此时栈和输出的情况如下：
    4
  4. 读到“*”，因为栈顶元素”+”优先级比” * “ 低，所以将” * “直接压入栈中。
  5. 读到c，直接输出。
    此时栈和输出情况如下：
    5
  6. 读到” + “，因为栈顶元素” * “的优先级比它高，所以弹出” * “并输出， 同理，栈中下一个元素” + “优先级与读到的操作符” + “一样，所以也要弹出并输出。然后再将读到的” + “压入栈中。
    此时栈和输出情况如下：
    6
  7. 下一个读到的为”(“，它优先级最高，所以直接放入到栈中。
  8. 读到d，将其直接输出。
    此时栈和输出情况如下：
    7
  9. 读到” * “，由于只有遇到” ) “的时候左括号”(“才会弹出，所以” * “直接压入栈中。
  10. 读到e，直接输出.
    此时栈和输出情况如下:
    8
  11. 读到” + “，弹出” * “并输出，然后将”+”压入栈中。
  12. 读到f，直接输出。
    此时栈和输出情况：
    9
  13. 接下来读到“）”，则直接将栈中元素弹出并输出直到遇到”(“为止。这里右括号前只有一个操作符”+”被弹出并输出。
    10
  14. 读到” * “，压入栈中。读到g，直接输出。
    11
  15. 此时输入数据已经读到末尾，栈中还有两个操作符“*”和” + “，直接弹出并输出。
    12

代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<stdio.h>
#include<stack>
#include<string.h>
#include<string>
using namespace std;

bool IsOpera(char a)
{
	if (a == '+' || a == '-' || a == '*' || a == '/')
		return true;
	return false;
}

string GetPost(char* str)
{
	stack<char> s1;
	string s = "";
	while (*str)
	{
		if (IsOpera(*str) == false && *str != '('&&*str != ')')
		{
			s += *str;
		}
		else if (*str == '(')
		{
			s1.push('(');
		}
		else if (*str == '+' || *str == '-')
		{
			while (s1.empty() == false&&s1.top()!='(')
			{
				s += s1.top();
				s1.pop();
			}
			s1.push(*str);
		}
		else if (*str == '*' || *str == '/')
		{
			while (s1.empty()==false&&(s1.top() == '*' || s1.top() == '/'))
			{
				s += s1.top();
				s1.pop();
			}
			s1.push(*str);
		}
		else if (*str == ')')
		{
			while (s1.top() != '(')
			{
				s += s1.top();
				s1.pop();
			}
			s1.pop();
		}
		str++;
	}
	while (s1.empty() == false)
	{
		s += s1.top();
		s1.pop();
	}
	return s;
}



double Compute(string str)
{
	stack<double> s2;
	for (int i = 0; i<str.length(); i++)
	{
		if (IsOpera(str[i]))
		{
			double a = s2.top();
			s2.pop();
			double b = s2.top();
			s2.pop();
			if (str[i] == '+')
				s2.push(a + b);
			else if (str[i] == '-')
				s2.push(b - a);
			else if (str[i] == '*')
				s2.push(a*b);
			else
				s2.push(b / a);
		}
		else
			s2.push(str[i] - '0');
	}
	return s2.top();
}

int main()
{

	char str1[100];
	while (gets(str1))
	{
		string str2 = GetPost(str1);
		printf("%f\n", Compute(str2));
	}
	return 0;
}