中缀表达式转后缀表达式（基于C++）

中缀表达式转后缀表达式

以a + b * c + ( d * e + f ) * g为例

• 基于堆栈的算法

  1. 从左到右扫描表达式，如果是操作数则直接输出。

     ​

  2. 如果扫描到的字符是一个操作符，分三种情况：

     （1）如果堆栈是空的，直接将操作符存储到堆栈中（push it）

     ​

     （2）如果该操作符的优先级大于堆栈出口的操作符，就直接将操作符存储到堆栈中（push it）

     ​

     （3）如果该操作符的优先级低于堆栈出口的操作符，就将堆栈出口的操作符导出（pop it）, 直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中（push）。

     ​

  3. 如果遇到的操作符是左括号"（”，就直接将该操作符输出到堆栈当中。该操作符只有在遇到右括号“)”的时候移除。这是一个特殊符号该特殊处理。

     ​

  4. 如果扫描到的操作符是右括号“）”，将堆栈中的操作符导出（pop）到output中输出，直到遇见左括号“（”。将堆栈中的左括号移出堆栈（pop ）。继续扫描下一个字符。

     ​

  5. 如果输入的中缀表达式已经扫描完了，但是堆栈中仍然存在操作符的时候，我们应该讲堆栈中的操作符导出并输入到output 当中。

     ​

代码实现

//中缀表达式转后缀表达式
queue InfixToSuffix(char arr[]) {
    stack stack;
    queue queue;
    map map;
    map['+'] = 1;
    map['-'] = 1;
    map['*'] = 2;
    map['/'] = 2;
    map['('] = 0;
    for (int i = 0; i < strlen(arr); ++i) {
        if (arr[i] >= '0' && arr[i] <= '9') {//如果是操作数直接进入输出队列
            queue.push(arr[i]);
        } else {
            if (stack.empty() || (map[arr[i]] > map[stack.top()]) && arr[i] != ')') {//如果该操作符优先级大于栈顶操作符优先级，压栈
                stack.push(arr[i]);
            } else if (map[arr[i]] <= map[stack.top()] && map[stack.top()] != 0 && arr[i] != ')' && arr[i] != '(') {//如果该操作符的优先级低于堆栈出口的操作符，就将堆栈出口的操作符导出, 直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中。
                while (map[arr[i]] <= map[stack.top()] && stack.top() != '(') {
                    queue.push(stack.top());
                    stack.pop();
                    if (stack.empty())break;
                }
                stack.push(arr[i]);
            } else if (arr[i] == '(') {//如果是左括号，直接压栈
                stack.push(arr[i]);
            } else if (arr[i] == ')') {//如果是右括号，循环弹栈直到遇到左括号
                while (stack.top() != '(') {
                    queue.push(stack.top());
                    stack.pop();
                }
                stack.pop();//将左括号弹栈
            } else exit(0);
        }
    }
    while (!stack.empty()) {//如果遍历完后栈不为空，则将栈内所有元素弹出
        queue.push(stack.top());
        stack.pop();
    }
    return queue;
}