Expression 数学表达式求值

问题描述

题目描述
给你一个数学表达式，请你求出它的值。
表达式中可能含有以下运算符：”+”、”-“、”“、”/“、”%”(取余)、”^”(指数)、”(“、”)”，其中优先级为: 括号 > “^” > “” = “/“ = “%” > “+” = “-“。

求解思路：

利用栈结构，将带括号的中缀表达式转为无括号的后缀表达式，再利用栈结构，对后缀表达式进行求值

中缀表达式转后缀表达式：
1、遇到数字时，不入栈，直接加入后缀表达式；
2、运算符：
（1）若为 ‘(‘，入栈；
（2）若为 ‘)’，则依次把栈中的的运算符出栈并加入后缀表达式中，直到出现’(‘，从栈中删除’(‘ ，但不加入后缀表达式；
（3）若为除括号外的其他运算符， 当其优先级高于除’(‘以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符并加入加入后缀表达式，直到一个比它优先级低的或者遇到了一个左括号为止。比较完成后，将当前运算符入栈
3、当扫描的中缀表达式结束时，栈中的的所有运算符出栈加入后缀表达式。

后缀表达式计算规则：
从左向右扫描，遇到数字压栈，遇到操作符，弹出栈顶的两个元素，先弹出的元素在右边，后弹出来的在左边，进行计算后，将结果压栈，再往后扫描，直到扫描结束，输出栈顶元素，即为最终结果。

实现

#include 
#include 
#include 
#include 

using namespace std;

int fun(char c)
{
	switch (c)
	{
		case '+':
			return 1;
		case '-':
			return 1;
		case '*':
			return 2;
		case '/':
			return 2;
		case '%':
			return 2;
		case '^':
			return 3;
		default:
			return -1;
	}
}

int main()
{
	string prefixExp;
	string suffixExp;
	getline(cin, prefixExp, '$');
	stack<char> midStack;
	stack<int> backStack;

	int len = prefixExp.length();
	for (int i = 0; i < len; i++)
	{
		if (prefixExp[i] == ' ')
		{
			continue;
		}
		if (prefixExp[i] >= '0' && prefixExp[i] <= '9')
		{
			suffixExp += prefixExp[i];
		}
		else
		{
			if (prefixExp[i] == '(')
			{
				midStack.push(prefixExp[i]);
			}
			else if (prefixExp[i] == ')')
			{
				while (midStack.size() != 0 && midStack.top() != '(')
				{
					char top = midStack.top();
					midStack.pop();
					suffixExp += top;
				}
				if (midStack.top() == '(')
				{
					midStack.pop();
				}
			}
			else
			{
				if (midStack.size() == 0)
				{
					midStack.push(prefixExp[i]);
				}
				else
				{
					char top = midStack.top();
					if (top != '(' && fun(prefixExp[i]) > fun(top))
					{
						midStack.push(prefixExp[i]);
					}
					else
					{
						while (midStack.size() > 0 && fun(top) >= fun(prefixExp[i]) && top != '(')
						{
							top = midStack.top();
							midStack.pop();
							suffixExp += top;
							if (midStack.size() > 0)
							{
								top = midStack.top();
							}
						}
						midStack.push(prefixExp[i]);
					}
				}
			}
		}
	}
	int stackLen = midStack.size();
	for (int i = 0; i < stackLen; i++)
	{
		char top = midStack.top();
		midStack.pop();
		suffixExp += top;
	}
	for (int i = 0; i < suffixExp.length(); i++)
	{
		if (suffixExp[i] >= '0' && suffixExp[i] <= '9')
		{
			backStack.push(suffixExp[i] - '0');
		}
		else
		{
			int top1 = 0;
			int top2 = 0;
			int top;
			if (backStack.size() > 0)
			{
				top1 = backStack.top();
				backStack.pop();
			}
			if (backStack.size() > 0)
			{
				top2 = backStack.top();
				backStack.pop();
			}
			switch (suffixExp[i])
			{
				case '+':
					top = top2 + top1;
					break;
				case '-':
					top = top2 - top1;
					break;
				case '*':
					top = top2 * top1;
					break;
				case '/':
					top = top2 / top1;
					break;
				case '%':
					top = top2 % top1;
					break;
				case '^':
					top = pow(top2, top1);
					break;
				default:
					return -1;
			}
			backStack.push(top);
		}
	}
	cout << backStack.top();
}

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154