表达式去括号

六 15 九月 2018

昨天做了道算法题，感觉有点局限性，今天重新修改了下。

数据格式

类型：string，

样例

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

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

代码

代码逻辑是：

  • 从第一个字符开始处理，将非'('的保存到ss中，直到遇到'('；
  • 调用process_bracket程序，继续处理后面的字符，直到遇到右括号，跳出循环；
  • 由于存在嵌套的括号，所以根据ss最后一个符号来判断正负号；
  • 如果是负号，则将'+'变成'-'，将'-'变成'+'，其余不变，保存到ss中；
  • 如果是正号，不做处理，保存到ss中；
  • 如果是左括号，迭代调用process_bracket程序。
#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;
}

blogroll