讨论一道表达式问题

玛玛哈哈

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由玛玛哈哈于 2021-1-29 05:29 编辑

想问一下大家这道题的思路或对我的代码指出哪里可以优化就更感激不尽了。回答的都加米。

给定一个只包含数字、加减乘除的算术表达式，要求按照运算顺序添加括号。所有数字大小都是 0~9，也就是只有个位。
例子:
输入: 1+4*3-2/1
输出: ((1+(4*3))-(2/1))

我尝试了两种解法, 都是有一部分数据超时了。一种是用双栈直接对中缀表达式操作, 另外一种是先转成后缀表达式再在后缀表达式上操作。

以下是我的代码: 这道题应该是线性复杂度才能全部过, 我觉得我的代码瓶颈应该是在每次string都需要拼接, 这个要是string很长的情况下开销很大(比如第一种解法中的第30行和第40行)。想问一下大家有没有办法解决这个问题或者说是有更好的解法。谢谢

这个是用双栈直接对中缀表达式操作

# include <iostream>
# include <stack>
# include <string>
using namespace std;
// 不转后缀表达式, 直接对中缀表达式求解
int getPrecedence(string &oprator) {
if (oprator == "+" || oprator == "-") return 1;
return 2;
}
bool priorityCompare(string &oprator1, string &oprator2) {
return getPrecedence(oprator1) >= getPrecedence(oprator2);
}
// expr：算术表达式
// 返回值：加上括号后的表达式
string solve(string &expr) {
stack<string> expStack;
stack<string> opStack;
for (char c: expr) {
string s = string(1, c);
if (isdigit(c)) {
expStack.push(s);
} else {
while (!opStack.empty() && priorityCompare(opStack.top(), s)) {
string op = opStack.top(); opStack.pop();
string right = expStack.top(); expStack.pop();
string left = expStack.top(); expStack.pop();
string newExp = "(" + left + op + right + string(")");
expStack.push(newExp);
}
opStack.push(s);
}
}
while (expStack.size() > 1) {
string op = opStack.top(); opStack.pop();
string right = expStack.top(); expStack.pop();
string left = expStack.top(); expStack.pop();
string newExp = "(" + left + op + right + string(")");
expStack.push(newExp);
}
return expStack.top();
}
int main() {
ios::sync_with_stdio(false);
string s;
cin >> s;
cout << solve(s) << '\n';
return 0;
}

复制代码

这个是先转成后缀再操作的代码:

# include <iostream>
# include <stack>
# include <vector>
# include <string>
using namespace std;
// 1. use shunting-yard algorithm to convert to RPN
// 2. use RPN evaluation algorithm to add brackets
class Op {
public:
char oprator;
int oprand;
bool isOprand;
Op() {}
Op(int oprand) {
this->isOprand = true;
this->oprand = oprand;
}
Op(char oprator) { // 运算符
this->isOprand = false;
this->oprator = oprator;
}
};
int getPrecedence(char &oprator) {
if (oprator == '+' || oprator == '-') return 1;
return 2;
}
bool priorityCompare(char &oprator1, char &oprator2) {
return getPrecedence(oprator1) >= getPrecedence(oprator2);
}
vector<Op> convertToRPN(string &expr) { // use shunting-yard algorithm
vector<Op> res;
stack<Op> opStack;
for (char c: expr) {
// check if is digit or not
Op curOp;
if (isdigit(c)) { // yes: push to back of res
curOp = Op(c - '0');
res.push_back(curOp);
} else { // no: while top of stack's precedence is no smaller than current operator => push to back of res
curOp = Op(c);
while (!opStack.empty() && priorityCompare(opStack.top().oprator, curOp.oprator)) {
res.push_back(opStack.top());
opStack.pop();
}
opStack.push(curOp);
}
}
while (!opStack.empty()) {
res.push_back(opStack.top());
opStack.pop();
}
return res;
}
// expr：算术表达式
// 返回值：加上括号后的表达式
string solve(string expr) {
stack<string> expStack;
vector<Op> rpn = convertToRPN(expr);
for (Op op: rpn) {
if (op.isOprand) {
expStack.push(to_string(op.oprand));
} else {
string right = expStack.top(); expStack.pop();
string left = expStack.top(); expStack.pop();
string newExp = "(" + left + string(1, op.oprator) + right + string(")");
expStack.push(newExp);
}
}
return expStack.top();
}
int main() {
ios::sync_with_stdio(false);
string s;
cin >> s;
cout << solve(s) << '\n';
return 0;
}

复制代码

usr_opta

本帖最后由 usr_opta 于 2021-1-29 14:30 编辑

玛玛哈哈发表于 2021-1-29 13:44
你能给我讲解一下term_size和terms_size具体是做什么的吗

简单起见只考虑+和*, - 和 / 一样。考虑 1*2+3+4*5*6。这里一共有3个term, "1*2", "3", "4*5*6", 分别有2, 1, 3个乘数，所以 terms_size 就是 [2,1,3]。

append_term 负责把一个形如 "((4*5)*6)" 的字符串添加到 ret. 由于我们知道是左结合，所以字符顺序肯定是
1.一串左括号，可能为空；2.一个数字；3a.一个符号；3b.一个数字；3c.一个右括号;3d.回到3a循环。数字和符号可以直接从输入里提取(append_ch).

+/-层级的处理一模一样，把步骤2和3b的输出数字改成输出term就是了。

肯定有更好理解的写法，但是时间复杂度是线性应该不能更低了。

usr_opta

因为输入不含括号，所以整个表达式肯定是 "(...(项+项)+项)+项)....+项)" 的形式. 每个项都只包含乘除，所以是纯粹的左结合。知道了总体结构以后可以预先扫描一遍，可以提前知道在每个地方需要加多少个连续的左括号，然后就可以顺序构造输出了。据说用 string.append() 会比用 operator+() 快:

#include <iostream>
#include <string>
#include <vector>
using namespace std;
string add_parenthesis(string s) {
vector<int> terms_size;
int term_size = 1;
for (char ch : s) {
switch (ch) {
case '*':
case '/':
term_size++;
break;
case '+':
case '-':
terms_size.push_back(term_size);
term_size = 1;
break;
}
}
terms_size.push_back(term_size);
string ret;
int ch_idx = 0;
int term_idx = 0;
auto append_ch = [&]{ ret.append({s[ch_idx++]}); };
auto append_term = [&]{
int term_size = terms_size[term_idx++];
if (term_size == 1) {
append_ch();
} else {
ret.append(string(term_size-1, '('));
append_ch();
for (int i = 0; i < term_size-1; i++) {
append_ch();
append_ch();
ret.append(")");
}
}
};
if (terms_size.size() == 1) {
append_term();
} else {
ret.append(string(terms_size.size()-1, '('));
append_term();
for (int i = 0; i < terms_size.size()-1; i++) {
append_ch();
append_term();
ret.append(")");
}
}
return ret;
}
int main(int argc, char*argv[]) {
string s;
cin >> s;
cout << add_parenthesis(s) << endl;
return 0;
}

复制代码

玛玛哈哈

usr_opta 发表于 2021-01-28 19:05:29
因为输入不含括号，所以整个表达式肯定是 "(...(项+项)+项)+项)....+项)" 的形式. 每个项都只包含乘除，所以是纯粹的左结合。知道了总体结构以后可以预先扫描一遍，可以提前知道在每个地方需

谢谢你的回答和代码！我消化一下

玛玛哈哈

usr_opta 发表于 2021-01-28 19:05:29
因为输入不含括号，所以整个表达式肯定是 "(...(项+项)+项)+项)....+项)" 的形式. 每个项都只包含乘除，所以是纯粹的左结合。知道了总体结构以后可以预先扫描一遍，可以提前知道在每个地方需

你能给我讲解一下term_size和terms_size具体是做什么的吗

玛玛哈哈

usr_opta 发表于 2021-1-29 11:05
因为输入不含括号，所以整个表达式肯定是 "(...(项+项)+项)+项)....+项)" 的形式. 每个项都只包含乘除，所 ...

你好我理解啦, terms_size是在计算每一项里数字的个数。这个解法可以通过所有的数据, 学习到了, 再次感谢。想问一下层主是怎么想到或者分析的呢, 是否有类似的一类题型或者知识点可以让我加以练习或者是巩固呢？

usr_opta

玛玛哈哈发表于 2021-1-29 14:21
你好我理解啦, terms_size是在计算每一项里数字的个数。这个解法可以通过所有的数据, 学习到了, 再次感谢 ...

我觉得其实基本功还是很重要的，比方说如果学过逻辑学或者compiler相关的课程，可以立马看出输入是一个 sum of product 格式的表达式，进而联想到从加号切分。或者如果你尝试手动计算 1+1+1+1+1+...+1, 应该能比较容易观察到这个左结合的结构。

很多这种表达式的题和 compiler/AST/状态机有密切的关系，可以尝试了解下，不一定能帮你解题，但希望能给你一个不同的角度去理解题解。

玛玛哈哈

usr_opta 发表于 2021-01-28 23:06:29
我觉得其实基本功还是很重要的，比方说如果学过逻辑学或者compiler相关的课程，可以立马看出输入是一个 sum of product 格式的表达式，进而联想到从加号切分。或者如果你尝试手动计算 1+

感谢！有什么推荐的compiler课程吗？

[高频题] 讨论一道表达式问题

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

评分

评分

评分

浏览过的版块