华为OJ表达式求值

约定不等于承诺〃 2022-06-17 08:42 140阅读 0赞

<table style="border-spacing:0px; border-collapse:collapse; width:960px; margin-bottom:35px; table-layout:fixed; color:rgb(92,92,92); font-family:glober,'Helvetica Neue',Helvetica,Arial,'Lantinghei SC','Hiragino Sans GB','Microsoft YaHei','Wenquanyi Micro Hei',sans-serif; font-size:14px; line-height:20px"> 
 <tbody style=""> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 描述</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> <pre style="overflow:hidden; font-family:monospace,monospace; font-size:1em; white-space:pre-wrap; word-wrap:break-word; line-height:24px">给定一个字符串描述的算术表达式，计算出结果值。输入字符串长度不超过100，合法的字符包括”+,&nbsp;-,&nbsp;*,&nbsp;/,&nbsp;(,&nbsp;)”，”0-9”，字符串内容的合法性及表达式语法的合法性由做题者检查。本题目只涉及整型计算。
 
 
 <ul style="margin:0px; padding:0px; list-style:none">
 
 <li style="margin:0px; padding:0px; list-style:none">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;&nbsp;&nbsp;&nbsp;功能:&nbsp;对输入的字符串表达式进行求值计算，并输出结果。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;输入:String&nbsp;inputString：表达式字符串&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;返回:&nbsp;int&nbsp;：正常返回true，失败返回false&nbsp;&nbsp;&nbsp;&nbsp;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;boolean&nbsp;calculate(String&nbsp;inputString)&nbsp;&nbsp;&nbsp;&nbsp;{
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*在这里实现功能*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;true;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</li>
 
 <li style="margin:0px; padding:0px; list-style:none">获取计算结果（int型）&nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;int&nbsp;getResult()&nbsp;&nbsp;&nbsp;&nbsp;{
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*在这里实现功能*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;</li>
 
 </ul> </pre> </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 知识点</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 栈</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 运行时间限制</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 10M</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 内存限制</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 128</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输入</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 输入算术表达式 </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输出</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 计算出结果值 </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输入</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 400+5</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输出</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 405 true</td> 
 </tr> 
 </tbody> 
</table>

#include <iostream> 
 #include <vector>
 #include <string>
 #include <stack>
 #include <map>
 #include <algorithm>
 
 using namespace std;
 
 map<char, int> priority;//保存运算符优先级
 vector<string> vec;//保存后缀表达式
 //函数getExpression用于获取字符串的后缀表达式
 //输入：str中缀表达式字符串
 //输出：vec后缀表达式
 //算法参考网址：http://blog.csdn.net/u012507347/article/details/52245233
 
 void getExpression(string str)
 {
 	stack<char> s;	//保存运算符
 	for (int i = 0; i < str.length(); i++)
 	{
 		if (isalnum(str[i]))
 		{
 			string num;
 			while (isalnum(str[i]))
 			{
 				num.push_back(str[i]);
 				i++;
 			}
 			vec.push_back(num);
 			i--;
 		}
 		else if (str[i] == '(')
 		{
 			s.push(str[i]);
 		}
 			
 		else if (str[i] == ')')
 		{
 			while (s.top() != '(')
 			{
 				string tmp;
 				tmp.push_back(s.top());
 				vec.push_back(tmp);
 				s.pop();
 			}
 			s.pop();
 		}
 		else
 		{
 			if(!s.empty() && priority[s.top()] <= priority[str[i]] 
 				&& s.top() != '(')
 			{
 				string tmp;
 				tmp.push_back(s.top());
 				vec.push_back(tmp);
 				s.pop();
 				s.push(str[i]);			
 			}
 			else
 				s.push(str[i]);
 		}
 	}
 	while (!s.empty())
 	{
 		string tmp;
 		tmp.push_back(s.top());
 		vec.push_back(tmp);
 		s.pop();
 	}
 }
 
 //计算后缀表达式的结果
 int computerExp()
 {
 	stack<int> s;
 	for (int i = 0; i < vec.size(); i++)
 	{
 		if (isalnum(vec[i][0]))
 		{
 			int num = atoi(vec[i].c_str());
 			s.push(num);
 		}
 		else
 		{
 			int value1 = s.top();
 			s.pop();
 			int value2 = s.top();
 			s.pop();
 			int value3;
 			switch (vec[i][0])
 			{
 			case '+':
 				value3 = value2 + value1;
 				break;
 			case '-':
 				value3 = value2 - value1;
 				break;
 			case '*':
 				value3 = value2 * value1;
 				break;
 			case '/':
 				value3 = value2 / value1;
 				break;
 			}
 			s.push(value3);
 		}
 	}
 	return s.top();
 }
 
 void main()
 {
 	priority['+'] = 1;
 	priority['-'] = 1;
 	priority['*'] = 0;
 	priority['/'] = 0;
 	string str;
 	cin >> str;
 	getExpression(str);
 	cout << computerExp()<<endl;
 	cout << "true";
 }