中后缀表达式

2023-12-26 10:38:35

一、利用后缀表达式进行计算

1)解题思路

  1. 如果当前字符串是操作数,就将该操作数入栈;
  2. 如果当前字符串是操作符,就取栈顶的两个操作数进行运算(注意:第一个出栈的数为计算时的右操作数;第二个出栈的数为计算是的左操作数),并将运算结果重新入栈;
  3. 重复上面两个步骤,直到字符串遍历完:最后栈里面的值就是计算结果。

2)代码

int evalRPN(vector<string>& tokens) 
    {
        stack<int> st;
        // 遍历字符
        for(auto& e : tokens)
        {
            // 如果遇到的是运算符,取出栈中的两个元素运算,并将运算结果入栈
            if(e == "+" || e == "-" || e == "*" || e == "/")
            {
                int num2 = st.top();
                st.pop();
                int num1 = st.top();
                st.pop(); 
                if(e == "+")
                    st.push(num1+num2);
                if(e == "-")
                    st.push(num1-num2);
                if(e == "*")
                    st.push(num1*num2);
                if(e == "/")
                    st.push(num1/num2);
            }
            // 如果是操作数,如入栈
            else
            {
                st.push(stoi(e));
            }
        } 
        return st.top();
    }
};

3)注意点

如果当前字符串为操作数时,需要先使用 stoi() 函数将字符串转化为数字后,将其入栈。

题目链接:

150. 逆波兰表达式求值 - 力扣(LeetCode)

二、中缀表达式转后缀表达式

1)解题思路

  1. 如果当前字符为操作数,直接输出;
  2. 如果当前字符为操作符,判断当前栈是否为空:
    1. 如果栈为空,将该操作符入栈;
    2. 如果栈不为空,将该操作符与栈顶元素比较优先级:
      1. 如果当前操作符优先级高,入栈;
      2. 如果当前操作符优先级相等或较低,输出栈顶元素。

还需要考虑,括号带来的优先级问题:不能仅仅根据运算符本身的优先级进行比较。

这里有好几种处理方法,在这里我介绍一种:

  1. 遇到 ( 时,将它入栈,并且认为它的优先级是最低的,这样才能保证括号内部的操作符才能入栈;
  2. 同时遇到 ) 时,我们还是认为它的优先级是最低的,这样才能保证括号内部的操作符能够出栈进行计算,并且出栈 - 后,并且遇到( 后,将其出栈。
  3. 最后如果栈空也不进行入栈操作,并进行下一个操作的判断。

括号的特殊处理,总结一下:

  1. ()的优先级最低;
  2. ( 不进行优先级的比较,直接入栈;
  3. ) 进行比较,输出栈顶元素,直到遇到( 。

下面举个例子,模拟一个这个过程:

当将中缀表达式1+2*(4-5*2)+6/7转化为后缀表达式时,可以按照以下步骤进行:

  1. 创建一个空栈和一个空列表(用于存放后缀表达式)。

  2. 从左到右遍历中缀表达式中的每个元素,按照以下规则处理:

    • 遇到数字时,直接加入到后缀表达式列表中。

    • 遇到运算符时,分两种情况:

      • 如果栈为空或者栈顶元素为左括号,将当前运算符压入栈中。
      • 否则,如果当前运算符的优先级小于等于栈顶运算符的优先级,则将栈顶运算符弹出并加入到后缀表达式列表中,直到栈顶运算符的优先级小于当前运算符的优先级或者栈为空,然后将当前运算符压入栈中。
    • 遇到左括号时,将其压入栈中。

    • 遇到右括号时,依次弹出栈顶元素并加入到后缀表达式列表中,直到遇到左括号为止。注意:左右括号不应该加入到后缀表达式列表中。

  3. 如果中缀表达式已经遍历完毕,则将栈中剩余的运算符依次弹出并加入到后缀表达式列表中。

  4. 后缀表达式列表即为转换得到的后缀表达式。

以下是将中缀表达式1+2*(4-5*2)+6/7转化为后缀表达式的详细过程:

  1. 初始化栈和后缀表达式列表为空。

  2. 从左到右遍历中缀表达式:

    • 遇到字符'1',加入后缀表达式列表:['1']
    • 遇到字符'+',将其压入栈中:栈:['+']
    • 遇到字符'2',加入后缀表达式列表:['1', '2']
    • 遇到字符'*',将其压入栈中:栈:['+', '*']
    • 遇到字符'(',将其压入栈中:栈:['+', '*', '(']
    • 遇到字符'4',加入后缀表达式列表:['1', '2', '4']
    • 遇到字符'-',将其压入栈中:栈:['+', '*', '(', '-']
    • 遇到字符'5',加入后缀表达式列表:['1', '2', '4', '5']
    • 遇到字符'*',将其压入栈中:栈:['+', '*', '(', '-', '*']
    • 遇到字符'2',加入后缀表达式列表:['1', '2', '4', '5', '2']
    • 遇到字符')',弹出栈顶元素并加入后缀表达式列表,直到遇到左括号为止:['1', '2', '4', '5', '2', '*', '-']
    • 弹出左括号'('。
    • 遇到字符'+',将其压入栈中:栈:['+', '+']
    • 遇到字符'6',加入后缀表达式列表:['1', '2', '4', '5', '2', '*', '-', '6']
    • 遇到字符'/',将其压入栈中:栈:['+', '+', '/']
    • 遇到字符'7',加入后缀表达式列表:['1', '2', '4', '5', '2', '*', '-', '6', '7']
  3. 中缀表达式已经遍历完毕,将栈中剩余的运算符依次弹出并加入到后缀表达式列表中:['1', '2', '4', '5', '2', '*', '-', '6', '7', '/', '+', '+']

  4. 后缀表达式为1 2 4 5 2 * - * + 6 7 / +

这就是将中缀表达式1+2*(4-5*2)+6/7转化为后缀表达式的详细过程。

2)代码

#include <iostream>
#include <stack>
#include <string>
#include <vector>

bool isOperator(char ch) {
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}

int getPriority(char op) {
    if (op == '+' || op == '-')
        return 1;
    else if (op == '*' || op == '/')
        return 2;
    return 0;
}

std::vector<std::string> infixToPostfix(const std::string& infix) {
    std::vector<std::string> postfix;
    std::stack<char> opStack;

    for (unsigned i = 0; i < infix.length(); ++i) {
        char ch = infix[i];

        if (ch == ' ') {
            continue;
        }
        else if (isdigit(ch)) {
            std::string num;
            while (i < infix.length() && (isdigit(infix[i]) || infix[i] == '.')) {
                num += infix[i++];
            }
            --i;
            postfix.push_back(num);
        }
        else if (isOperator(ch)) {
            while (!opStack.empty() && opStack.top() != '(' &&
                   getPriority(opStack.top()) >= getPriority(ch)) {
                postfix.push_back(std::string(1, opStack.top()));
                opStack.pop();
            }
            opStack.push(ch);
        }
        else if (ch == '(') {
            opStack.push(ch);
        }
        else if (ch == ')') {
            while (!opStack.empty() && opStack.top() != '(') {
                postfix.push_back(std::string(1, opStack.top()));
                opStack.pop();
            }
            opStack.pop(); // Discard '('
        }
    }

    while (!opStack.empty()) {
        postfix.push_back(std::string(1, opStack.top()));
        opStack.pop();
    }

    return postfix;
}

int main() {
    std::string infixExpression = "1+2*(4-5*2)+6/7";
    std::vector<std::string> postfixExpression;

    postfixExpression = infixToPostfix(infixExpression);

    for (const auto& token : postfixExpression) {
        std::cout << token << " ";
    }
    std::cout << std::endl;

    return 0;
}

遇到 ( 时,将它入栈,并且认为它的优先级是最低的,这样才能保证括号内部的操作符才能入栈;

同时遇到 ) 时,我们还是认为它的优先级是最低的,这样才能保证括号内部的操作符能够出栈进行计算,并且出栈 - 后,并且遇到( 后,将其出栈,最后如果栈空也不进行入栈操作,并进行下一个操作的判断。

同时也可以使用增加一个flag标签的方法:

我们可以将这个flag初始化为0,只有遇到( 时,将flag = 1,通过flag的值判断下一个操作符的优先级,当flag = 1时,无论下一个操作符是什么,我们都认为它的优先级是高于此时栈顶操作符的,并进行入栈操作。当遇到)时,将flag置为0;

也可以使用递归,将()内部的表达式用一个新的栈进行计算,并将结果返回。

文章来源:https://blog.csdn.net/2201_75479723/article/details/134717046
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。