假设不含括号的表达式由单字母变量和双目四则运算符构成，试写一个算法，将一个通常书写形式且书写正确的表达式转换成逆波兰式。其中precede(char x,char y) 为判断x,y优先级,该算法可以

使用栈来实现逆波兰式转换：

1. 初始化一个空栈和一个空字符串，用于存储逆波兰式。

2. 从左到右扫描表达式，如果遇到数字或变量，直接将其加入逆波兰式字符串中。

3. 如果遇到运算符，判断其与栈顶运算符的优先级，如果栈顶运算符优先级高或相等，则将栈顶运算符弹出并加入逆波兰式字符串中，直到栈顶运算符优先级低于当前运算符或栈为空，然后将当前运算符压入栈中。

4. 如果遇到左括号，直接将其压入栈中。

5. 如果遇到右括号，则依次弹出栈顶运算符并加入逆波兰式字符串中，直到遇到左括号为止，左括号不加入逆波兰式字符串中。

6. 扫描完表达式后，如果栈中还有运算符，依次弹出并加入逆波兰式字符串中。

7. 返回逆波兰式字符串。

算法实现：

1. 初始化一个空栈和一个空字符串。

2. 从左到右扫描表达式，对于每个字符：

a. 如果是数字或变量，直接将其加入逆波兰式字符串中。

b. 如果是运算符：

i. 如果栈为空或栈顶为左括号，直接将当前运算符压入栈中。

ii. 如果栈顶为运算符且优先级高于或等于当前运算符，则弹出栈顶运算符并加入逆波兰式字符串中，重复此步骤直到栈为空或栈顶运算符优先级低于当前运算符，然后将当前运算符压入栈中。

c. 如果是左括号，直接将其压入栈中。

d. 如果是右括号，依次弹出栈顶运算符并加入逆波兰式字符串中，直到遇到左括号为止，左括号不加入逆波兰式字符串中。

3. 扫描完表达式后，如果栈中还有运算符，依次弹出并加入逆波兰式字符串中。

4. 返回逆波兰式字符串。

代码实现：

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

using namespace std;

int precede(char x, char y) {
    if ((x == '*' || x == '/') && (y == '+' || y == '-'))
        return 1;
    else
        return ;
}

string infix2postfix(string infix) {
    stack<char> s;
    string postfix = "";
    int len = infix.length();
    for (int i = ; i < len; i++) {
        char c = infix[i];
        if (isdigit(c) || isalpha(c)) {
            postfix += c;
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            while (!s.empty() && s.top() != '(' && precede(s.top(), c)) {
                postfix += s.top();
                s.pop();
            }
            s.push(c);
        } else if (c == '(') {
            s.push(c);
        } else if (c == ')') {
            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            if (!s.empty() && s.top() == '(')
                s.pop();
        }
    }
    while (!s.empty()) {
        postfix += s.top();
        s.pop();
    }
    return postfix;
}

int main() {
    string infix = "a+b*c-(d/e+f)*g";
    string postfix = infix2postfix(infix);
    cout << postfix << endl;
    return ;
}

输出结果为：abc*+de/f+g*-