要求输入只含有+,-,*,/,(,),和数字的字符串,输出结果
思路:
1 两个栈一个保存int型数字,一个保存char型运算符
2 指针指向字符串(程序中使用迭代器实现)
规则:
指针移动,遇到数字直接入栈
如果不是数字,如果是(递归,移动指针,新值入栈
如果是),移动指针,跳出做清算,
否则判断op栈顶是否为空
为空直接入栈。
如果不为空,判断当前字符如果是+ -
看栈顶是+ - 就运算上次,本次的op入栈
看栈顶是* / ,不运算,本次的op入栈
如果不为空,判断当前字符如果是* /
看栈顶是 + -,本次op入栈
看栈顶是*/,运算上次,本次op入栈
当指针到末尾时,看栈顶是否为空,不为空就一直做运算
【编程题目_四则运算器】
//手写四则运算
namespace calculator
{
char getSopTop(stack &s)
{
if (s.empty())
{
return 'n';
}
else
{
return s.top();
}
} //使用optop运算,得到结果入snum栈
//sop.pop();
void use_op_push_value(stack &snum, stack &sop, char &optop)
{
int num2 = snum.top();
snum.pop();
int num1 = snum.top();
snum.pop();
int newnum = 0;
switch (optop)
{
case '*':
newnum = num1 * num2;
break;
case '/':
newnum = num1 / num2;
break;
case '+':
newnum = num1 + num2;
break;
case '-':
newnum = num1 - num2;
break;
}
sop.pop();
snum.push(newnum);
} int cal(string::iterator &it, string &str)
{
stack snum;
stack sop;
while (it != str.end())
{
char optop = getSopTop(sop);
char cur = (*it);
if (cur > '0' && cur < '9'){
//是数字
int temp = 0;
string strtemp(it, str.end());
size_t offset = 0;
temp = stoi(strtemp, &offset);
it += offset;
snum.push(temp);
}
else{
//是op
if (cur == '('){
int ret = cal(++it, str);
snum.push(ret);
}
else if (cur == ')'){
it++;
break;
}
else{
//是+ - * /
if (optop == 'n'){
//op栈空
sop.push(cur);
it++;
}
else{
//op栈不空
if (cur == '+' || cur == '-'){
if (optop == '+' || optop == '-'){
use_op_push_value(snum, sop, optop);
it++;
//再getOpTop一次,看看1+2*3+4*5+6-->1+6+20+6,也可以不使用
/* while ((optop = getSopTop(sop)) != 'n')
{
sop.pop();
int num2 = snum.top();
snum.pop();
int num1 = snum.top();
snum.pop();
int newnum = 0;
switch (optop)
{
case '+':
newnum = num1 + num2;
break;
case '-':
newnum = num1 - num2;
break;
}
}*/
sop.push(cur);
}//optop + -
else{
//optop * /
use_op_push_value(snum, sop, optop);
sop.push(cur);
it++;
}//optop * /
}//cur + -
else if (cur == '*' || cur == '/')
{
if (optop == '+' || optop == '-'){
sop.push(cur);
it++;
}
else{
use_op_push_value(snum, sop, optop);
sop.push(cur);
it++;
}//optop * /
}// cur * /
}// 是+ - * /
}//是op + - * /
}//end of 是()+-*/
}//end of while//到结尾了
while (!sop.empty()){
char optop = getSopTop(sop);
use_op_push_value(snum, sop, optop);
}
return snum.top();
}//end of cal int func(string &str){
string::iterator it = str.begin();
int ret = cal(it, str);
cout << ret << endl;
return ret;
} void test(){
string str = "100*(1+1)-200*2";
int ret = func(str);
}
}