神奇的读入
查看原帖
神奇的读入
76495
chichow楼主2020/10/21 23:35

建议直接cin,少考虑。。。

~scanf("%c",&ch),;
scanf("%c",&ch) != EOF
if (ch == '\n') break;

这三都试过了,不行,直接全WA,我吐了。顺便附上代码,解法为构建表达式树

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#define EL puts("")
using namespace std;
char str[110];
int table[7][7] = {
    // +   -   *   /   ^   (   )
    {  1,  1, -1, -1, -1, -1,  1},  // +
    {  1,  1, -1, -1, -1, -1,  1},  // -
    {  1,  1,  1,  1, -1, -1,  1},  // *
    {  1,  1,  1,  1, -1, -1,  1},  // /
    {  1,  1,  1,  1, -1, -1,  1},  // ^
    { -1, -1, -1, -1, -1, -1,  0},  // (
    {  1,  1,  1,  1,  1,  1,  1}   // )
};
int getVal(char ch){
    switch(ch){
        case '+': return 10;
        case '-': return 11;
        case '*': return 12;
        case '/': return 13;
        case '^': return 14;
        case '(': return 15;
        case ')': return 16;
        default : return ch-'0';
    }
}
struct Node{
    int val,lson,rson,type;
    bool op;
}node_st[110];
int node_top=0,root;
stack<int> st_op,st_nu;
int calc(int pa,int pb,int opp){
    int v1 = node_st[pa].val;
    int v2 = node_st[pb].val;
    switch(node_st[opp].type){
        case 10: return v1+v2;
        case 11: return v1-v2;
        case 12: return v1*v2;
        case 13: return v1/v2;
        case 14: return pow((double)v1,(double)v2);
    }
}
void suo(){ //计算并连接已有节点
    int opp = st_op.top();st_op.pop();
    int pb  = st_nu.top();st_nu.pop();
    int pa  = st_nu.top();st_nu.pop();
    int re = calc(pa,pb,opp);
    node_st[opp].lson = pa;
    node_st[opp].rson = pb;
    node_st[opp].val = re;
    st_nu.push(opp);
}
void pushCh(int fch){
    if (fch<10){
        node_st[node_top].val = fch;
        node_st[node_top].op = false;
        st_nu.push(node_top++);
    }else{
        LOOP:
        if (st_op.empty()){
            node_st[node_top].type = fch;
            node_st[node_top].op = true;
            st_op.push(node_top++);
        }else switch(table[node_st[st_op.top()].type-10][fch-10]){
            case -1:
                node_st[node_top].type = fch;
                node_st[node_top].op = true;
                st_op.push(node_top++);break;
            case  0:
                st_op.pop();break;
            case  1:
                suo();
                goto LOOP;
        }
    }
}
void printTree(int x){
    if (!node_st[x].op){
        printf("%d ",node_st[x].val);
        return ;
    }
    printTree(node_st[x].lson);
    printTree(node_st[x].rson);
    char ch;
    switch(node_st[x].type){
        case 10 : ch='+';break;
        case 11 : ch='-';break;
        case 12 : ch='*';break;
        case 13 : ch='/';break;
        case 14 : ch='^';break;
    }
    printf("%c ",ch);
}
void workit(int x){
    int lson = node_st[x].lson;
    int rson = node_st[x].rson;
    if (node_st[lson].op) workit(lson);
    if (node_st[rson].op) workit(rson);
    node_st[x].op = false;
    printTree(root);
    EL;
}
int main(){
    cin>>str;
    for (int i=0; i<strlen(str); i++){
        pushCh(getVal(str[i]));
    }
    while (!st_op.empty()){
        suo();
    }
    root = st_nu.top();
    printTree(root);EL;
    workit(root);
    return 0;
}
2020/10/21 23:35
加载中...