【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数

本文涉及知识点

动态规划汇总
字符串表达式栈

LeetCode2019 解出数学表达式的学生分数

给你一个字符串 s ，它只包含数字 0-9 ，加法运算符 ‘+’ 和乘法运算符 ‘’ ，这个字符串表示一个合法的只含有个位数数字的数学表达式（比方说 3+5 $\star$ 2）。有 n 位小学生将计算这个数学表达式，并遵循如下运算顺序：
按照从左到右的顺序计算乘法，然后
按照从左到右的顺序计算加法。
给你一个长度为 n 的整数数组 answers ，表示每位学生提交的答案。你的任务是给 answer 数组按照如下规则打分：
如果一位学生的答案等于表达式的正确结果，这位学生将得到 5 分。
否则，如果答案由一处或多处错误的运算顺序计算得到，那么这位学生能得到 2 分。
否则，这位学生将得到 0 分。
请你返回所有学生的分数和。
示例 1：
输入：s = “7+3 $\star$ 1 $\star$ 2”, answers = [20,13,42]
输出：7
解释：如上图所示，正确答案为 13 ，因此有一位学生得分为 5 分：[20,13,42] 。
一位学生可能通过错误的运算顺序得到结果 20 ：7+3=10，10 $\star$ 1=10，10 $\star$ 2=20 。所以这位学生得分为 2 分：[20,13,42] 。
所有学生得分分别为：[2,5,0] 。所有得分之和为 2+5+0=7 。
示例 2：
输入：s = “3+5 $\star$ 2”, answers = [13,0,10,13,13,16,16]
输出：19
解释：表达式的正确结果为 13 ，所以有 3 位学生得到 5 分：[13,0,10,13,13,16,16] 。
学生可能通过错误的运算顺序得到结果 16 ：3+5=8，8 $\star$ 2=16 。所以两位学生得到 2 分：[13,0,10,13,13,16,16] 。
所有学生得分分别为：[5,0,0,5,5,2,2] 。所有得分之和为 5+0+0+5+5+2+2=19 。
示例 3：
输入：s = “6+0 $\star$ 1”, answers = [12,9,6,4,8,6]
输出：10
解释：表达式的正确结果为 6 。
如果一位学生通过错误的运算顺序计算该表达式，结果仍为 6 。
根据打分规则，运算顺序错误的学生也将得到 5 分（因为他们仍然得到了正确的结果），而不是 2 分。
所有学生得分分别为：[0,0,5,0,0,5] 。所有得分之和为 10 分。
提示：
3 <= s.length <= 31
s 表示一个只包含 0-9 ，‘+’ 和 '’ 的合法表达式。
表达式中所有整数运算数字都在闭区间 [0, 9] 以内。
1 <= 数学表达式中所有运算符数目（‘+’ 和 ‘*’） <= 15
测试数据保证正确表达式结果在范围 [0, 1000] 以内。
n == answers.length
1 <= n <= 10⁴
0 <= answers[i] <= 1000

动态规划

num依次记录运算数，op依次记录运算符。利用栈实现一个简单的运算类，来计算正确结果。
利用动态规划来实现计算所有错误运算符的结果。
$\begin{cases} 正确结果为[0,1000] \\ 加上任意数只会不边或变大\\ 乘以0以外的数，只会变大或不变\\ \end{cases}$ $\rightarrow$ 中间结果>1001和1000完全一样 $\begin{cases} 结果相同 & 乘了0 \\ 大于answers的最大值1000 &没有乘0 \\ \end{cases}$

动态规划的状态表示

dp[len][i]表示num[i,i+len)所有运算顺序正确或错误可能的结果。

动态规划的转移方程

dp[len][i] = 追加 $_{len1:1}^{len-1}$ dp[len1][i] 加（或乘) dp[len-len1][i+len1]

动态规划的初始值

dp[1][i] = num[i]

动态规划的填表顺序

len 从2到大，以确保填表顺序。
i从小到大。

动态规划的返回值

正确结果得5分，dp.back()[0]中的值得2分。

代码

核心代码

class Solution {
public:
	int scoreOfStudents(string s, vector<int>& answers) {
		CExpression exp;
		for (const char& ch : s)
		{
			if (('+' == ch) || ('*' == ch))
			{
				exp.AddOpe(ch);
			}
			else
			{
				exp.AddNum(ch - '0');
			}
		}
		const int iAns = exp.DoAddSub();
		int num[16];
		char ope[15];
		for (int i = 0; i < s.length(); i++)
		{
			if (i & 1)
			{
				ope[i / 2] = s[i];
			}
			else
			{
				num[i / 2] = s[i] - '0';
			}
		}
		int n = (s.length() + 1) / 2;
		vector<vector<unordered_set<int> >> dp(n+1, vector<unordered_set<int>>(n));
		for (int i = 0; i < n; i++)
		{
			dp[1][i].emplace(num[i]);
		}
		for (int len = 2; len <= n; len++)
		{
			for (int i = 0; i + len <= n; i++)
			{
				for (int len1 = 1; len1 < len; len1++)
				{
					for (const auto& n1 : dp[len1][i])
					{
						for (const auto& n2 : dp[len - len1][i + len1])
						{
							const int ret = ('+' == ope[i + len1 - 1]) ? (n1 + n2) : (n1 * n2);
							dp[len][i].emplace((ret>1001)?1001:ret);
						}
					}
				}
			}
		}
		int iRet = 0;
		for (const auto& ans : answers)
		{
			if (iAns == ans)
			{
				iRet += 5;
			}
			else if (dp.back()[0].count(ans))
			{
				iRet += 2;
			}
		}
		return iRet;
	}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	string s;
	vector<int> answers;
	{
		Solution sln;
		s = "7+3*1*2", answers = { 20, 13, 42 };
		auto res = sln.scoreOfStudents(s,answers);
		Assert(res,7);
	}

	{
		Solution sln;
		s = "3+5*2", answers = { 13, 0, 10, 13, 13, 16, 16 };
		auto res = sln.scoreOfStudents(s, answers);
		Assert(res, 19);
	}

	{
		Solution sln;
		s = "6+0*1", answers = { 12, 9, 6, 4, 8, 6 };
		auto res = sln.scoreOfStudents(s, answers);
		Assert(res, 10);
	}
}

2023年2月版

class Solution {
public:
int scoreOfStudents(string s, vector& answers) {
m_c = s.length();
const int iVilid = GetVilidAns(s);
vector < vector<std::unordered_set>> vLenPosErrAns(m_c + 1, vector<std::unordered_set>(m_c));
for (int len = 1; len <= m_c; len += 2)
{
for (int iPos = 0; iPos+len-1 < m_c; iPos += 2)
{
if (1 == len)
{
vLenPosErrAns[len][iPos].insert(s[iPos] - ‘0’);
continue;
}
for (int leftLen = 1;; leftLen += 2)
{
const int iRightLen = len - 1 - leftLen;
if (iRightLen <= 0)
{
break;
}
CalSet(vLenPosErrAns[len][iPos], vLenPosErrAns[leftLen][iPos], s[iPos + leftLen], vLenPosErrAns[iRightLen][iPos + leftLen + 1]);
}
}
}
int iRet = 0 ;
for (int i = 0; i < answers.size(); i++)
{
if (iVilid == answers[i])
{
iRet += 5;
continue;
}
if (vLenPosErrAns[m_c][0].count(answers[i]))
{
iRet += 2;
}
}
return iRet;
}
void CalSet(std::unordered_set& setResult, const std::unordered_set& set1, char chOpe, const std::unordered_set& set2)
{
for (auto it : set1)
{
for (auto ij : set2)
{
int iResult = it + ij;
if (‘’ == chOpe )
{
iResult = itij;
}
if (iResult <= 1000)
{
setResult.insert(iResult);
}
}
}
}
int GetVilidAns(string s)
{
stack staNum;
stack staOpe;
for (const auto& ch : s)
{
if ((’’ == ch) || (‘+’ == ch))
{
staOpe.push(ch);
}
else
{
staNum.push(ch-‘0’);
if ((staNum.size() >= 2) && staOpe.size()&&(''== staOpe.top()))
{
int t1 = staNum.top();
staNum.pop();
int t2 = staNum.top();
staNum.pop();
staNum.push(t1*t2);
staOpe.pop();
}
}
}

	 while (staNum.size() >= 2)
	 {
		 int t1 = staNum.top();
		 staNum.pop();
		 int t2 = staNum.top();
		 staNum.pop();
		 staNum.push(t1+t2);
		 staOpe.pop();
	 }
	 return staNum.top();
 }
 int m_c;

};

2023年7月

class Solution {
public:
int scoreOfStudents(string s, vector& answers) {
for (const auto& ch : s)
{
if ((‘+’ == ch) || (‘’ == ch))
{
m_staOpes.emplace(ch);
}
else
{
const int iNum = ch - ‘0’;
if (m_staOpes.size() && ('’ == m_staOpes.top()))
{
const int iPre = m_staNums.top();
m_staNums.pop();
m_staNums.emplace(iPre * iNum);
m_staOpes.pop();
}
else
{
m_staNums.emplace(iNum);
}
}
}
while (m_staOpes.size())
{
int iNext = m_staNums.top();
m_staNums.pop();
const int iPre = m_staNums.top();
m_staNums.pop();
m_staOpes.pop();
m_staNums.emplace(iPre + iNext);
}
m_c = s.length() / 2 + 1;
m_dp.assign(m_c, vector<set>(m_c));
for (int i = 0; i < m_c; i++)
{
m_dp[i][i] .emplace( s[i * 2] - ‘0’);
}
for (int len = 2; len <= m_c; len++)
{
#define END (begin + len - 1)
for (int begin = 0; END < m_c; begin++)
{
for (int mid = begin ; mid < END; mid++)
{
Ope(m_dp[begin][END], m_dp[begin][mid], m_dp[mid + 1][END],s[mid*2+1]);
}
}
}
int iScore = 0;
for (const auto& ans : answers)
{
if (ans == m_staNums.top())
{
iScore += 5;
}
else if (m_dp[0].back().count(ans))
{
iScore += 2;
}
}
return iScore;
}
void Ope(set& res, const set& pre, const set& next,const char& ch )
{
for (const auto& it : pre)
{
for (const auto& ij : next)
{
int iRes = (‘+’ == ch) ? (it + ij) : (it * ij);
if (iRes > 1000)
{
break;
}
res.emplace(iRes);
}
}
if (res.empty())
{
res.emplace(1001);
}
}
stack m_staNums;
stack m_staOpes;
int m_c;
vector<vector<set>> m_dp;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。