普通の数式では
a + b
と書くところを、演算子(プラス記号)の順序を変えて、
+ a b
と書きます。
これだって数式は表せるわけですね。Lisp などでは (+ a b) となります。
+ + a b c
これだと、どうなるでしょう。
a + b + c
こうですね。
逆ポーランド記法というのあります。逆ポーランド記法であると、a + b が
a b +
となります。日本語だと思えばいいんですね。「a と b を足す」という形です。
a b c + +
これだと、「a と b と c と足して、また足す」となります。
以下は、逆ポーランド記法の数式を処理するプログラムです。
→ reverse-polish-notaion
#括弧の処理を追加しました。(2016-07-10)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <sstream> | |
#include <stack> | |
#include <stdlib.h> | |
using namespace std; | |
string parse() | |
{ | |
string str; | |
stack<string> stk; | |
char c; | |
int x,y,z; | |
while(cin >> c, c != '=') | |
{ | |
switch(c) | |
{ | |
case '(': | |
stk.push(parse()); | |
break; | |
case ')': | |
if(!stk.empty()) | |
{ | |
return stk.top(); | |
} | |
break; | |
case '+': | |
case '*': | |
case '-': | |
case '/': | |
x=atoi(stk.top().c_str());stk.pop(); | |
y=atoi(stk.top().c_str());stk.pop(); | |
if(c=='+') | |
z=x+y; | |
else if(c=='-') | |
z=y-x; | |
else if(c=='*') | |
z=x*y; | |
else if(c=='/') | |
{ | |
if(x!=0) | |
z=y/x; | |
else | |
{ | |
cout << "Error: Division by zero" << endl; | |
throw 0; | |
} | |
} | |
stk.push(static_cast<ostringstream*>( &(ostringstream() << z) )->str()); | |
break; | |
default: | |
cin.putback(c); cin >> str; | |
stk.push(str); | |
break; | |
} | |
} | |
if(!stk.empty()) | |
{ | |
return stk.top(); | |
} | |
throw 0; | |
} | |
int main() | |
{ | |
try | |
{ | |
cout << parse(); | |
} | |
catch(int e) | |
{ | |
cout << "Parse error" << endl; | |
} | |
return 0; | |
} |