這個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

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["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

• 4 年前