简单计算器的实现

川长思鸟来 2022-08-02 09:34 229阅读 0赞

计算器

问题描述： 输入一个简单四则运算表达式字符串，计算该表达式的值   
  
  
注：   
1、表达式只含 +, -, \*, /, (, ), 四则运算符   
2、表达式数值只包含整数(0-9)，每个操作数可以是多位，且不会出现0作为除数的情况   
3、要考虑加减乘除按通常四则运算规定的计算优先级   
4、除法用整数除法，即仅保留除法运算结果的整数部分。比如80/3=26。输入表达式保证无0作为除数情况发生   
5、输入字符串一定是符合题意合法的表达式，其中只包括数字字符和四则运算符字符，除此之外不含其它任何字符，不会出现计算溢出情况  
  
  
要求实现函数：    
int calculate(int len,char \*expStr)   
  
  
【输入】 int len: 字符串长度； char \*expStr: 表达式字符串；   
【输出】 无   
【返回】 计算结果    
• 示例    
1） 输入：char \*expStr = “-3\*(-200)-(-3\*(-5-2\*10)/(4+3-17)\*9)”

函数返回：663  
2） 输入：char \*expStr = “8/3\*3”

函数返回：6

#include "stdafx.h"
    #include<vector>
    #include<deque>
    #include<iostream>
    using namespace std;
    
    
    char*vec2char(vector<char>vec, char*str)
    {
    	char*s = str;
    	vector<char>::iterator it;
    	it = vec.begin();
    	while (it != vec.end())
    		*(s++) = *(it++);
    	*s = '\0';
    	return str;
    }
    
    //计算不带括号的表达式的值
    int calculate_without_bracket(vector<char>&substr)
    {
    	vector<char>::iterator it, it1, it2, iter;
    	char*str = new char[100];
    	it = substr.begin();
    	while (it != substr.end())
    	{
    		deque<int>bb;
    		deque<int>::iterator p;
    		int aa;
    		//因为每次去括号时，都会对多个“-”
    		//号进行合并，这里不会出现多于两个“-”相连的情况
    		if (*substr.begin() == '-')
    		{
    			if (*(substr.begin() + 1) == '-')
    			{
    				substr.erase(substr.begin(), substr.begin() + 2);
    				it = substr.begin();
    			}
    		}
    		if (*it == '*' || *it == '/')
    		{
    			bool flag1 = false;
    			bool flag2 = false;
    			int f1 = 0, f2 = 0;
    			it1 = it - 1;
    
    			int gg = 0;
    			while (*it1 - '0' >= 0 && *it1 - '0' <= 9 && it1 - substr.begin() >= 0)
    			{
    				gg++;
    				bb.push_front(*it1 - '0');
    				if (it1 == substr.begin())
    					break;
    				it1--;
    			}
    			if (it1 != substr.begin())
    			{
    				if (*it1 == '-')
    				{
    					if (*(it1 - 1) == '-')
    						if (it1 - 1 == substr.begin())
    						{
    							substr.erase(substr.begin(), substr.begin() + 2);
    							it = substr.begin() + gg;
    							it1 = substr.begin();
    						}
    						else
    						{
    							it1 = it1 - 2;
    							substr.erase(it1 + 1, it1 + 3);
    							substr.insert(it1 + 1, '+');
    							it1 = it1 + 2;
    							it = it1 + gg;
    						}
    					else if (*(it1 - 1) == '+')//这一次的乘除运算之前不可能出现别的“*”或“/”
    					{
    						it1 = it1 - 2;
    						substr.erase(it1 + 1, it1 + 3);
    						substr.insert(it1 + 1, '-');
    						it1 = it1 + 2;
    						it = it1 + gg;
    					}
    					else
    						it1++;
    				}
    
    			}
    			else if (it1 == substr.begin() && *it1 == '-')
    				it1++;
    			it2 = it + 1;
    			if (*it2 == '-')
    			{
    				flag1 = true;
    				it2++;
    			}
    			p = bb.begin();
    			while (p != bb.end())
    			{
    				f1 = *p + 10 * f1;
    				++p;
    			}
    			while (it2 != substr.end() && *it2 - '0' >= 0 && *it2 - '0' <= 9)
    			{
    				f2 = 10 * f2 + (*it2 - '0');
    				it2++;
    			}
    			if (*it == '*')
    				aa = f1*f2;
    			else
    				aa = f1 / f2;
    			if (flag1)
    				aa = -aa;
    			char*ss = new char[100];
    			_itoa(aa, ss, 10);
    			if (it1 == substr.begin())
    			{
    				int c = 0;
    				substr.erase(it1, it2);
    				while (*ss != '\0')
    				{
    					substr.insert(substr.begin() + c, *ss);
    					++ss;
    					++c;
    				}
    				it = substr.begin();
    			}
    			else
    			{
    				int c = 0;
    				iter = it1 - 1;
    				substr.erase(it1, it2);
    				while (*ss != '\0')
    				{
    					substr.insert(iter + 1 + c, *ss);
    					++ss;
    					++c;
    				}
    				//substr.insert(iter + 1, aa+'0');
    				it = iter + 1;
    			}
    		}
    		else
    		{
    
    			it++;
    		}
    		//if (substr.size() == 1)
    		// return (*substr.begin() - '0');
    	}
    	it = substr.begin();
    	while (it != substr.end())
    	{
    
    		deque<int>bb;
    		deque<int>::iterator p;
    		int aa;
    		if (*substr.begin() == '-')
    		{
    			if (*(substr.begin() + 1) == '-')
    			{
    				substr.erase(substr.begin(), substr.begin() + 2);
    
    			}
    			else
    			{
    				bool flag2 = false;
    				int f1 = 0, f2 = 0;
    				it1 = substr.begin() + 1;
    
    				while (*it1 - '0' >= 0 && *it1 - '0' <= 9)
    				{
    					bb.push_back(*it1 - '0');
    					it1++;
    					if (it1 == substr.end())
    					{
    						char*src = new char[100];
    						return atoi(vec2char(substr, src));
    					}
    				}
    
    				p = bb.begin();
    				while (p != bb.end())
    				{
    					f1 = *p + 10 * f1;
    					++p;
    				}
    				it = it1;
    				it2 = it + 1;
    				if (*it2 == '-')//因为每次去括号时，都会对多个“-”
    					//号进行合并，这里不会出现多于两个“-”相连的情况
    				{
    					it2++;
    					flag2 = true;
    				}
    				while (it2 != substr.end() && *it2 - '0' >= 0 && *it2 - '0' <= 9)
    				{
    					f2 = 10 * f2 + (*it2 - '0');
    					it2++;
    				}
    				if (*it == '+')
    					if (flag2)
    						aa = -f1 - f2;
    					else
    						aa = -f1 + f2;
    				else
    					if (flag2)
    						aa = -f1 + f2;
    					else
    						aa = -f1 - f2;
    				char*ss = new char[100];
    				_itoa(aa, ss, 10);
    				int c = 0;
    				substr.erase(substr.begin(), it2);
    				while (*ss != '\0')
    				{
    					substr.insert(substr.begin() + c, *ss);
    					++ss;
    					++c;
    				}
    				//substr.insert(substr.begin(), aa + '0');
    				it = substr.begin();
    
    			}
    		}
    		else if
    			//因为每次都是从左到右一次只计算两个数，除了第一个符号是“-”外，另一种
    			//情况下第一个操作数一定是正数，只需考虑第二个操作数的符号
    			(*it == '+' || *it == '-')
    		{
    			bool flag1 = false;
    			int f1 = 0, f2 = 0;
    			it1 = it - 1;
    			it2 = it + 1;
    			if (*it2 == '-')
    			{
    				flag1 = true;
    				it2++;
    			}
    			while (*it1 - '0' >= 0 && *it1 - '0' <= 9 && it1 - substr.begin() >= 0)
    			{
    				bb.push_front(*it1 - '0');
    				if (it1 == substr.begin())
    					break;
    				it1--;
    			}
    			if (it1 != substr.begin())
    				it1++;
    			p = bb.begin();
    			while (p != bb.end())
    			{
    				f1 = *p + 10 * f1;
    				++p;
    			}
    			while (it2 != substr.end() && *it2 - '0' >= 0 && *it2 - '0' <= 9)
    			{
    				f2 = 10 * f2 + (*it2 - '0');
    				it2++;
    			}
    			if (*it == '+')
    				if (flag1)
    					aa = f1 - f2;
    				else
    					aa = f1 + f2;
    			else
    				if (flag1)
    					aa = f1 + f2;
    				else
    					aa = f1 - f2;
    			char*ss = new char[100];
    			_itoa(aa, ss, 10);
    			if (it1 == substr.begin())
    			{
    				int c = 0;
    				substr.erase(it1, it2);
    				while (*ss != '\0')
    				{
    					substr.insert(substr.begin() + c, *ss);
    					++ss;
    					++c;
    				}
    				//substr.insert(substr.begin(), aa + '0');
    				it = substr.begin();
    			}
    			else
    			{
    				//iter = it - 2;
    				//substr.erase(it - 1, it + 2);
    				//substr.insert(iter + 1, aa + '0');
    				//it = iter + 1;
    				int c = 0;
    				iter = it1 - 1;
    				substr.erase(it1, it2);
    				while (*ss != '\0')
    				{
    					substr.insert(iter + 1 + c, *ss);
    					++ss;
    					++c;
    				}
    				it = iter + 1;
    			}
    
    		}
    		else
    		{
    			it++;
    		}
    	}
    
    	return atoi(vec2char(substr, str));
    }
    
    
    
    
    
    //去括号，每次找到第一对连续匹配的括号，然后用calculate_without_bracket函数
    //计算括号里的表达式的值，计算后的结果插入原表达式，返回true。
    //如果原表达式没有括号，返回false
    bool erase_bracket(vector<char>&str)
    {
    	int size = str.size();
    	bool flag = false;
    	int k = 0;
    	int m, n;
    	vector<char>::iterator it, it1, it2;
    	it = str.begin();
    	while (k < size)
    	{
    		if (str[k] == '(')
    		{
    			m = k;
    			k++;
    			while (str[k] != '('&&str[k] != ')')
    				k++;
    			if (str[k] == ')')
    			{
    				n = k;
    				flag = true;
    				break;
    			}
    			else if (str[k] == '(')
    			{
    				k--;
    			}
    			
    		}
    		else
    		{
    			k++;
    		}
    	}
    	if (flag)
    	{
    		vector<char>sub;
    		for (int i = m+1; i < n ; i++)
    			sub.push_back(str[i]);
    		calculate_without_bracket(sub);
    		it = it + m - 1;
    		for (int i = 0; i < n + 1 - m;i++)
    		str.erase(it + 1, (it + 2 ));
    		int k = 0;
    		int len = sub.size();
    		while (k < len)
    		{
    			str.insert(it + k + 1, sub[k]);
    			k++;
    		}
    	}
    
    	return flag;
    }
    
    
    
    /*vector<char>char2vec(vector<char>&vec, char*str)
    {
    	while (*str != '\0')
    	{
    		vec.push_back(*str);
    		++str;
    	}
    	return vec;
    }*/
    
    
    //整体表达式计算函数，每次调用erase_bracket函数先计算括号里的值
    //直到消除所有的括号，最后调用calculate_without_bracket计算剩下的无括号表达式的值
    int calculate(int len, char *expStr)
    {
    	vector<char>str;
    	for (int i = 0; i < len; i++)
    		str.push_back(expStr[i]);
    	bool flag = true;
    
    	while (flag)
    	{
    		flag = erase_bracket(str);
    	}
    
    	return calculate_without_bracket(str);
    
    }
    
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	/*vector<int>aa;
    	vector<int>::iterator it,ite;
    	for (int i = 0; i < 5; i++)
    	aa.push_back(i);
    	it = aa.begin()+3;
    	ite = it -2;
    	aa.erase(it-1,it+1);
    	aa.insert(ite+1, 9);*/
    
    
    	vector<char>vec;
    	//char2vec(vec, "2+10-30-2*9/4+3-7*9");
    	//cout << calculate_without_bracket(vec) << endl;
    	//int len=strlen("2+(5-14-2)*9/(4+3-17)*9");
    	int len = strlen("-3*(-200)-(-3*(-5-2*10)/(4+3-17)*9)");
    	cout << calculate(len, "-3*(-200)-(-3*(-5-2*10)/(4+3-17)*9)");
    
    	system("pause");
    	return 0;
    }