计算器
问题描述： 输入一个简单四则运算表达式字符串，计算该表达式的值
注：
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;
}