表达式去括号

2018-11-16  本文已影响0人  Joe_WQ

date: 2018-9-15
昨天做了道算法题,感觉有点局限性,今天重新修改了下。

数据格式

类型:string

样例

输入:a+b-(c+d+(e+f-(c+d))-(g-e))-d,没有空格,而且只有'+'、'-'、'('和')'。

输出结果:a+b-c-d-e-f+c+d+g-e-d

代码

代码逻辑是:

#include <iostream>

using namespace std;
void process_bracket(string::iterator &, string &);
string process_1(string expre) {
    string ss;
    // 从第一个开始处理,遇到'('号交给process_bracket,括号里的正负号由ss的最后一个字符决定
    for (auto ci = expre.begin(); ci != expre.end(); ++ci) {
        if (*ci != '(')
            ss.push_back(*ci);
        else
            process_bracket(ci, ss);
    }
    return ss;
}

void process_bracket(string::iterator &is, string &ss) {
    if (ss[ss.size()-1] == '-') { // 处理括号前是-号的情况,由于是可能存在嵌套括号,这里选择的是ss的正负号
        is++;
        while (*is != ')') { // 处理括号里面所有的字符
            switch (*is) {
            case '-':
                ss.push_back('+');
                break;
            case '+':
                ss.push_back('-');
                break;
            case '(': // 存在嵌套,迭代求解
                process_bracket(is, ss);
                break;
            default:
                ss.push_back(*is);
                break;
            }
            ++is;
        }
    } else { //处理括号前是+号的情况
        is++;
        while (*is != ')') {
            switch (*is) {
            case '(':
                process_bracket(is, ss);
                break;
            default:
                ss.push_back(*is);
                break;
            }
            ++is;
        }
    }
}

int main() {
    string s("a+b-(c+d+(e+f-(c+d))-(g-e))-d");
    cout << process_1(s);

    return 0;
}
上一篇 下一篇

猜你喜欢

热点阅读