首页 > 代码库 > 中缀表达式转换为后缀表达式(1042)

中缀表达式转换为后缀表达式(1042)

2024-09-15 20:09:39   218人阅读

描述

中缀表达式是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) * 3 ， 即2 1 + 3 *。利用栈结构，将中缀表达式转换为后缀表达式。(测试数据元素为单个字符)


input

中缀表达式

output

后缀表达式

样例输入

A+(B-C/D)*E

样例输出

ABCD/-E*+

 

这道题我的一个思路为首先扫描字符串，遇到非运算符先输出，或者是再用一个字符串存起来，碰到操作符后，判断是哪种操作符，我认为乘除的优先级大于加减，且相同操作符先扫描到的优先级高，这是我用了一个栈来保存这些操作符，若栈顶元素的优先级高于扫描到的元素，则出栈输出，然后扫描到的字符入栈，碰到左括号直接入栈，碰到右括号直接出栈到左括号为止。

综上所述，遇到加减号直接把栈中元素全部出栈或者遇到左括号就停，遇到乘除号和左括号直接入栈，遇到右括号出栈到左括号。

具体代码如下：

 

#include<iostream>

#include<string>
#include<stack>
using namespace std;
 
bool isOperator(char ch){
    string s="+-*/()#";
    for(int i=0;i<7;i++){
        if(ch==s[i])return true;
    }
    return false;
}
 
int main(){
    string str;
    stack<char>s;
    cin>>str;
    s.push(‘#‘);
    for(int i=0;i<str.size();i++){
        if(!isOperator(str[i]))
        {
            cout<<str[i];
        }
        else if(str[i]==‘+‘||str[i]==‘-‘){
            while(s.top()!=‘#‘&&s.top()!=‘(‘){
                cout<<s.top();
                s.pop();
            }
            s.push(str[i]);
        }else if(str[i]==‘)‘){
            while(s.top()!=‘(‘){
                cout<<s.top();
                s.pop();
            }
            s.pop();
        }else{
            s.push(str[i]);
        }
    }
    while(s.top()!=‘#‘){
        cout<<s.top();
        s.pop();
    }
     
    return 0;
}

 

中缀表达式转换为后缀表达式(1042)


联系
我们