AND(A,B,OR(C,D,E)) 转换

背景

一天，朋友问我 AND(A,B,OR(C,D,E)) 该怎么转换成 A&B&(C|D|E), 当时回复他用栈就可以了吧，后来自己实现了一下，
才发现没这么简单。下面是我实现的思路：

• 先把符号入栈，这里的符号指的是 AND 或者是 OR 转换成 & 或 |, 我们每次拿栈顶的符号进行括号内的转换就行了
• 遇到（ 就将里面的值 加进数组中，遇到 )就将这个数组入栈， 我们称这个叫数据栈
• 最后将数据栈与符号栈结合

以下是完整代码：

代码

// console.log(convertString('AND(A,B,OR(C,D,E))')); // "A&B&(C|D|E)"我想实现这个convertstring有什么好的思路吗
function merge(a, b) {
  function mergeExpr(arr, sep, level) {
    if (arr.length === 0) {
      return ''
    }
    const target = arr.splice(0, 1)[0]
    const current = target + (arr.length > 0 ? sep : '')
    return current + (arr.length > 0 ? '(' + mergeExpr(arr, b[level + 1], level + 1) + ')' : '')
  }
  return mergeExpr(a, b[0], 0)
}

const convertString = (string) => {
  const length =  string.length

  const MAP = {
    'AND': '&',
    'OR': '|'
  }

  // 记录符号
  const stack1 = []

  //记录数据， 每一个（） 里面的数据 都是一个数组， 所以他是一个二维数组
  const stack2 = []

  // 表示栈中的层级 没遇到一个（ 就加一， 遇到 ） 就减一
  let level = -1;
  let tempString = ''
  for (let i = 0; i < length - 1; i++) {
    const nextChar =  string[i + 1]
    const currentChar =  string[i]

    if (currentChar === '(' || currentChar === ',' || currentChar === ')') {
      continue
    }
    tempString = tempString + currentChar

    // 如果下一个是字母 是 （  那么就是一个完整的字符串, 也就是 AND 或者 OR
    if (nextChar === '(') {
      level = level + 1
      stack2.push([])
      stack1.push(MAP[tempString])
      tempString = ''
      continue
    } else if (nextChar === ',') {
      const topData = stack2[level]
      topData.push(tempString)
      tempString = ''
    } else if (nextChar === ')') {
      const topData = stack2[level]
      topData.push(tempString)
      tempString = ''
      level = level - 1
    }
  }

  const k = []
  for (let i = 0; i < stack1.length; i++) {
    const character = stack1[i]
    k.push(`${stack2[i].join(character)}`)
  }
  return merge(k, stack1.slice(0, -1))
}

const a = convertString('AND(A,B,OR(C,D,E,AND(F,G)))')
const b = convertString('OR(AND(A,B,C),D,E)')
const c = convertString('AND(A,B,J,OR(C,D,E,AND(F,G),K))')

console.log(a)
console.log(b)
console.log(c)

第二版

上面那版是有bug， 以下这一版是通过 通过递归的操作， 获取括号内的内容， 进行操作，如果还有括号，那么继续进行递归

function convertString(string) {
  const MAP = {
    'AND': '&',
    'OR': '|'
  }

  function calculate(string, character) {
    const length = string.length;
    let res = '' 
    let tempString = ''
    let tempCharacter = character

    for (let i = 0; i < length; i++) {
      const currentChar = string[i];
      const nextChar = string[i + 1] ;

      if (currentChar === '(') {
        let j = i;
        let cnt = 0
        for (;i < length; i++) {
          if (string[i] === '(') ++cnt;
          if (string[i] === ')') --cnt;
          if (cnt === 0) break;
        }
        res +=  '(' + calculate(string.substring(j + 1, i), tempCharacter) + ')';
        // 如果递归后，后面仍然有其他内容，那么添加上当前的 符号
        res += i < length - 1 ? character : ''
        tempString = ''
        tempCharacter = character
        continue
      }

      if (currentChar === ',') {
        continue
      }

      tempString += currentChar;

      if (nextChar === '(') {
        tempCharacter = MAP[tempString];
        tempString = ''
        continue
      }

      if (nextChar === ',') {
        res += tempString + tempCharacter
        tempString = ''
        continue
      }

      if (nextChar === ')' || typeof nextChar === 'undefined') {
        res += tempString
        tempString = ''
      }
    }

    return res
  }

  const final = calculate(string, "")

  return final.slice(1, -1)
}

const a = convertString('AND(A,B,OR(C,D,E,AND(F,G)))');
const e = convertString('OR(AND(A,B,OR(C,D,E,AND(F,G))),I,OR(AND(A,B,C),D,E))');

const b = convertString('OR(AND(A,B,C),D,E)');

const d = convertString('OR(AND(A,B),AND(C,D))');
const c = convertString('AND(A,B,J,OR(C,D,E,AND(F,G),K))');