SDUT数据结构PTA专题（实验三）题解 （最近有点忙，尽快更完！）

• 7-1 进制转换
• 7-2 表达式转换
• 7-3 后缀式求值
• 7-4 括号匹配

答案：

#include 
#include 
#include
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair
#define x first
#define y second
#define PLL pair
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={-1, 0, 1, 0};
int dy[]={0, 1, 0, -1};
using namespace std;
 
char bi[M],oc[M],he[M];   // 数组模拟栈
int nb,no,nh;  // 栈顶指针
 
void get_bin(int n){ // 变为二进制
    while(n){
        bi[++nb]=n%2+'0';
        n/=2;
    }
    while(nb) cout<>n;
    if(!n){  // 特判0
        cout<<"0 0 0"<>t;
    while(t--) solve();
    return 0;
}

坑点：

1. 这里的数字可能是小数、负数(负号和数字是一起输出的)或带正号的数字
2. 最卡格式的一种情况就是运算符和右括号连续出现的情况比如2+(+5)-1,要仔细考虑输出格式的处理

答案：

#include
#define ll long long
#define eb emplace_back
const int N = 2e5 + 10;
using namespace std;

string st[N];
int top;
vectorvp;

inline void solve(){
    string s;
    cin>>s;
    bool tag=0;
    for(int i=0;i 
7-3 后缀式求值 
答案：
 
#include
#define ll long long
#define eb emplace_back
const int N = 2e5 + 10;
using namespace std;

double st[N];
int top;

inline void solve(){
    string s;
    getline(cin,s);
    stringstream ss(s);
    while(ss>>s){
        if(isdigit(s[0])||s.size()>1) st[++top]=stod(s);  // 将数字压栈
        else{
            if(s=="+") st[top-1]+=st[top],top--;  // 加法操作
            else if(s=="-") st[top-1]-=st[top],top--;  // 减法操作
            else if(s=="*") st[top-1]=st[top-1]*1.0*st[top],top--;  // 乘法操作
            else if(s=="/") st[top-1]=st[top-1]*1.0/st[top],top--;  // 除法操作
        }
    }
    cout< 
7-4 括号匹配 
答案：
 
#include
#define ll long long
#define eb emplace_back
const int N = 2e5 + 10;
using namespace std;

char st[N];
int top;

inline void solve(){
    string s;
    getline(cin,s);  // 防止出现空格
    bool tag=0;
    for(int i=0;i