匿名使用者
匿名使用者 發問時間: 電腦與網際網路程式設計 · 4 年前

這個c++題,不用stack,有辦法做嗎?

題目大概是這樣的

For examples, “ADD 2 3” is 5 and “MUL 5 2” is 10.

The complicated expressions are similar to the simple expressions except that the

operands are not restricted to integers. The operands of complicated expressions can be

another simple or complicated expressions.

For example 1, “ADD MUL 2 3 4” is 2*3+4 = 10.

For example 2, “ADD 4 MUL 3 3” is 4+3*3 = 13.

For example 3, “ADD MUL 2 3 MUL 4 5” is 2*3+4*5 = 26.

The functions include ADD, SUB, MUL, MAX, and MIN. The following table shows

the function behaviors.

Function Behavior

ADD a b a + b

SUB a b a - b

MUL a b a * b

MAX a b (a>=b) ? a : b

MIN a b (a<b) ? a : b

Sample Input

ADD 2 MAX ADD 2 3 MUL 2 3

Sample Output

8

我還不會用stack, 所以我嘗試了用function和if else等方式,但都會有地方卡住~~

可以給我一個方向嗎?概念大概是什麼?

我在input的地方 不知道要如何判斷是 運算(EX:ADD) 還是數字卡很久

他們的data type不同,如何解決?

已更新項目:

若是引用#include<fstream>的話

sscanf(op0.c_str(),"%d",&ret);

for(p=b; scanf("%c",p) && isspace(*p); );

for(++p; scanf("%c",p) && !isspace(*p); ++p);

sscanf和scanf怎麼改??

3 個解答

評分
  • 4 年前
    最佳解答

    // very easy indeed!

    // recursion is always a good sub for stack. Simple and easy to read.

    #include<stdio.h>

    #include<stdlib.h>

    #include<string.h>

    #include<iostream>

    #include<map>

    using namespace std;

    typedef int (*FPTR)(void);

    typedef std::map<string, FPTR> MAP;

    MAP M;

    int str2uint(

    string op0

    ){

    int ret;

    sscanf(op0.c_str(),"%d",&ret);

    return ret;

    }

    int getNext(

    ){

    char b[32]={'\0'}, *p;

    for(p=b; scanf("%c",p) && isspace(*p); );

    for(++p; scanf("%c",p) && !isspace(*p); ++p);

    *p = '\0';

    string s(b);

    if(M.end() == M.find(s)) return str2uint(s);

    return ::M[s]();

    }

    int ADD(void){ return getNext() + getNext();}

    int SUB(void){ return getNext() - getNext();}

    int MUL(void){ return getNext() * getNext();}

    int MAX(void){ int op0 = getNext(), op1 = getNext(); return (op0 >= op1) ? op0 : op1; }

    int MIN(void){ int op0 = getNext(), op1 = getNext(); return (op0 < op1) ? op0 : op1; }

    int main(){

    ::M["ADD"] = ADD;

    ::M["SUB"] = SUB;

    ::M["MUL"] = MUL;

    ::M["MAX"] = MAX;

    ::M["MIN"] = MIN;

    for(;cout << getNext() << endl;);

    return 0;

    }

    CPP$ ./stk

    ADD 2 MAX ADD 2 3 MUL 2 3

    8

    ADD 2 MAX ADD 2 3 MUL 2 -12

    7

    ADD 2 SUB 2 3

    1

    MUL 13 MUL 23 12

    3588

  • 4 年前

    這題如果不用stack的話可以把input當作tree考慮,再用dfs從下而上求得答案 (結構見附圖,先將最底的運算完成後再解決上層的運算),但解題理念上還是跟stack一樣 (而事實上dfs的實行概念上也是要用到stack) 。

    這種做法有點兒簡單複雜化,所以建議樓主還是先學一學stack再做這題吧,而且我畢竟stack簡單又實用。

    至於input的方面,考慮到input一定會符合格式,可以先把全段input當作string處理,再視乎空白後的位置是數字還是英文字作判斷。

    這裏附個使用stack的代碼,若是有哪裏不明白歡迎追問。http://ideone.com/t07MvE

    Attachment image
  • 4 年前

還有問題?馬上發問,尋求解答。