ACM比赛整理
Polish notation
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1754 Accepted Submission(s): 280
Problem Description
Reverse Polish notation (RPN) is a method for representing expressions in which the operator symbol is placed after the arguments being operated on.
Polish notation, in which the operator comes before the operands, was invented in the 1920s by the Polish mathematician Jan Lucasiewicz.
In the late 1950s, Australian philosopher and computer scientist Charles L. Hamblin suggested placing the operator after the operands and hence created reverse polish notation.
RPN has the property that brackets are not required to represent the order of evaluation or grouping of the terms.
RPN expressions are simply evaluated from left to right and this greatly simplifies the computation of the expression within computer programs.
As an example, the arithmetic expression (3+4)*5 can be expressed in RPN as 3 4 + 5 *.
Reverse Polish notation, also known as postfix notation, contrasts with the infix notation of standard arithmetic expressions in which the operator symbol appears between the operands. So Polish notation just as prefix notation.
Now, give you a string of standard arithmetic expressions, please tell me the Polish notation and the value of expressions.
Input
There're have multi-case. Every case put in one line, the expressions just contain some positive integers(all less than 100, the number of integers less than 20), bi-operand operators(only have 3 kinds : +,-,*) and some brackets'(',')'.
you can assume the expressions was valid.
Output
Each case output the Polish notation in first line, and the result of expressions was output in second line.
all of the answers are no any spaces and blank line.the answer will be not exceed the 64-signed integer.
Sample Input
1+2-3*(4-5)
1+2*(3-4)-5*6
Sample Output
Case 1:
- + 1 2 * 3 - 4 5
6
Case 2:
- + 1 * 2 - 3 4 * 5 6
-31
波兰表示法
问题描述
反向波兰表示法(RPN)是一种表示表达式的方法，其中操作符符号放在被操作的参数之后。
波兰表示法是由波兰数学家Jan Lucasiewicz在20世纪20年代发明的，在这种表示法中，运算符先于操作数。
在20世纪50年代末，澳大利亚哲学家和计算机科学家Charles L. Hamblin建议将运算符放在操作数之后，因此创建了反向波兰表示法。
RPN有一个特性，即括号不需要表示求值或术语分组的顺序。
RPN表达式简单地从左到右计算，这大大简化了计算机程序中表达式的计算。
例如，算术表达式(3+4)*5在RPN中可以表示为3 4 + 5 *。
反向波兰表示法，也称为后缀表示法，与标准算术表达式的中缀表示法形成对比，在中缀表示法中，操作符符号出现在操作数之间。波兰表示法就是前缀表示法。
现在，给你一串标准算术表达式，请告诉我波兰符号和表达式的值。
输入
有实现。每一种情况放入一行，表达式只包含一些正整数(都小于100，整数的数量小于20)，双操作数操作符(只有3种:+，-，*)和一些括号'('，')'。
您可以假设表达式是有效的。
输出
每个case在第一行输出波兰符号，在第二行输出表达式的结果。
所有答案都没有空格和空白行。答案不会超过64符号整数。
Sample Input
1+2-3*(4-5)
1+2*(3-4)-5*6
Sample Output
Case 1:
- + 1 2 * 3 - 4 5
6
Case 2:
- + 1 * 2 - 3 4 * 5 6
-31
嗨，这道题是个好题，既考了字符串操作函数，又考了栈的使用
遵循一个操作符旁边有两个操作数，用两个栈，一个操作符栈和一个操作数栈，模拟操作的出波兰式
代码要做的是：（利用运算符的优先级）
1、初始化一个操作符栈，一个操作数栈
2、反向开始，因为是求波兰式，如果遇到数字，将数字这段字符串进入操作数栈；如果操作符栈为空，直接将操作符入栈，遇到‘）’，直到遇到‘（’，将操作符栈中的操作符取出，每取出一个操作符，就从操作数栈中取出两个字符串，组合成新的字符串再次入操作数栈，（主要遵循一个操作符左右必有两个操作数或表达式）；如果将要进入操作数栈的优先级大于里面的，直接入栈，如果小于栈里的操作符，则取出一个操作符，必取出两个操作数。
3、最后还是利用栈将表达式计算出来
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<map>
using namespace std;
#define N 105
typedef long long LL;
map<char,int>mp;
map<char,string>mt;
const string sample = "+-*/()";
void Init()
{
mp['+'] = 1;mp['-'] = 1;mp['*'] = 2;
mp['/'] = 2;mp['('] = 0;mp[')'] = 0;
mt['+'] = "+";mt['-'] = "-";
mt['*'] = "*";mt['/'] = "/";
}
stack<string>num; //储存操作数
stack<char>opt; //储存操作符
bool judge(char ch)
{
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
string getstring(string s)
{
while(!num.empty()) num.pop();
while(!opt.empty()) opt.pop();
string newstring;
for(int i = s.size() - 1;i >= 0;--i)
{
if(isdigit(s[i]))
{
int index = s.find_last_of(sample,i);
string numstring = s.substr(index + 1,i - index);
//cout << numstring << endl;
num.push(numstring);
i = index + 1;
}
else{
if(s[i] == ')')
opt.push(s[i]);
else{
if(!opt.empty() && s[i] == '(')
{
while(opt.top() != ')')
{
char ptr = opt.top();
opt.pop();
string x = num.top();num.pop();
string y = num.top();num.pop();
string tmp = mt[ptr] + " " + x + " " + y;
//cout << tmp << endl;
num.push(tmp);
}
opt.pop();
}
else{
if(!opt.empty() && mp[s[i]] >= mp[opt.top()])
opt.push(s[i]);
else{
//cout << s[i] << " " << opt.top() << endl;
if(!opt.empty() && mp[s[i]] < mp[opt.top()])
{
while(!opt.empty() && mp[s[i]] < mp[opt.top()])
{
char ptr = opt.top();
opt.pop();
string x = num.top();num.pop();
string y = num.top();num.pop();
string tmp = mt[ptr] + " " + x + " " + y;
//cout << tmp << endl;
num.push(tmp);
}
opt.push(s[i]);
}
else{
if(opt.empty() && judge(s[i]))
opt.push(s[i]);
}
}
}
}
}
}
while(!opt.empty())
{
char ptr = opt.top();
opt.pop();
string x = num.top();num.pop();
string y = num.top();num.pop();
string tmp = mt[ptr] + " " + x + " " + y;
//cout << tmp << endl;
num.push(tmp);
}
newstring = num.top();
return newstring;
}
LL cal(string s)
{
stack<LL>sta;
for(int i = s.size() - 1;i >= 0;--i)
{
//if()
if(isdigit(s[i]))
{
int index = s.find_last_of(' ',i);
string tmp = s.substr(index + 1,i - index);
LL n;
sscanf(tmp.c_str(),"%lld",&n);
sta.push(n);
i = index + 1;
}
else{
if(s[i] != ' ' && judge(s[i]))
{
LL n = sta.top();sta.pop();
LL m = sta.top();sta.pop();
switch(s[i])
{
case '+':sta.push(n + m);break;
case '-':sta.push(n - m);break;
case '*':sta.push(n * m);break;
case '/':sta.push(n / m);break;
}
}
}
}
return sta.top();
}
int main()
{
/*string s = "456+*-/";
cout << atoi(s.c_str()) << endl;*/
string s;
s = "456";
//初始化操作符的优先级
Init();
int k = 0;
//cout << judge('-') << endl;
while(cin >> s)
{
k++;
printf("Case %d:\n",k);
string tmp = getstring(s);
cout << tmp << endl;
cout << cal(tmp) << endl;
}
return 0;
}
