【试解leetcode算法题--求解方程】<题目描述>
求解一个给定的方程,将x以字符串"x=#value"的形式返回。该方程仅包含’+’,’ - '操作,变量 x 和其对应系数。
- 如果方程没有解,请返回“No solution”。
- 如果方程有无限解,则返回“Infinite solutions”。
- 如果方程中只有一个解,要保证返回值 x 是一个整数。
https://leetcode-cn.com/problems/solve-the-equation
<理明思路>
※解释:
- string solveEquation(string):题目给出初始函数。
- string anlz_equal(string,int):输入原始字符串,参数0取方程左边的式子并返回;参数1取方程右边的式子并返回。
- void anlz_numbr(string,int):将字符串(0=左边 1=右边)的字符串转换为数字并入栈。(其中默认将所有系数放在等式左边,所有常数放在等式右边)
- stack1< int>:存放系数的栈。
- stack2< int>:存放常数的栈。
- 最终将方程化为ax=b型(若有解),即可解出。
文章图片
<样例代码>
ps:本题只是按照自己的思路来编辑代码,执行用时32ms,相比之下并不是多么出彩的算法。。。
#include
#include
#include
#include
using namespace std;
class Solution {
public:
void function(string str,int n);
//将字符串变成数字、入栈。
string anlz_equal(string equation,int n);
//分割字串,参数0:等号左,参数1:等号右。
string solveEquation(string equation) {int a=0,b=0;
//a=系数之和;b=常数之和;
double c;
string ans = "x=";
stringstream num;
function(anlz_equal(equation,0),0);
//方程左边常数&系数入栈。
function(anlz_equal(equation,1),1);
//方程右边常数&系数入栈。while( !xishu.empty() )
{
a += xishu.top();
//系数之和
xishu.pop();
}
while( !changshu.empty() )
{
b += changshu.top();
//常数之和
changshu.pop();
}
if(a==0&&b!=0)
return "No solution";
if(a==0&&b==0)
return "Infinite solutions";
c = (double)b/(double)a;
num << c;
//将整数转换为字符串。
if(num.str() == "-0")
num.str="0"
ans += num.str();
return ans;
}
private:
stack xishu;
stack changshu;
};
void Solution::function(string str,int n)
{
int a=0,j=1;
switch(n)
{
case 0://等式左边:系数为本身,常数为相反数。
{
for(int i=str.length()-1;
i>=0;
i--)
{
if(str[i] == 'x' && i==0)
{
xishu.push(1);
break;
}if(str[i] == 'x')
{
i--;
if(str[i]=='+')
{xishu.push(1);
continue;
}
else if(str[i]=='-')
{xishu.push(-1);
continue;
}
while(str[i]!='-')
{
if(str[i]=='+') break;
a += (str[i]-48)*j;
j *= 10;
i--;
if(i<0) break;
}
j=1;
if(str[i]=='-')
a = (-1)*a;
//取负数。
xishu.push(a);
a=0;
continue;
}
if(str[i] != 'x')//等号左边常数部分
{
while(str[i]!='-')
{
if(str[i]=='+') break;
a += (str[i]-48)*j;
j *= 10;
i--;
if(i<0) break;
}
j=1;
if(str[i]=='-')
a = (-1)*a;
//取负数。
changshu.push(-a);
a=0;
continue;
}
}
}//end case 0
break;
case 1://等式右边:常数为本身,系数为相反数。
{
for(int i=str.length()-1;
i>=0;
i--)
{
if(str[i] == 'x' && i==0)
{
xishu.push(-1);
break;
}
if(str[i] == 'x')
{
i--;
if(str[i]=='+')
{xishu.push(-1);
continue;
}
else if(str[i]=='-')
{xishu.push(1);
continue;
}while(str[i]!='-')
{
if(str[i]=='+') break;
a += (str[i]-48)*j;
j *= 10;
i--;
if(i<0) break;
}
j=1;
if(str[i]=='-')
a = (-1)*a;
//取负数。
xishu.push(-a);
a=0;
continue;
}
if(str[i] != 'x')//等号左边常数部分
{
while(str[i]!='-')
{
if(str[i]=='+') break;
a += (str[i]-48)*j;
j *= 10;
i--;
if(i<0) break;
}
j=1;
if(str[i]=='-')
a = (-1)*a;
//取负数。
changshu.push(a);
a=0;
continue;
}
}
}//end case 1
break;
default:
cout<<"error"<