正文
【面试笔试算法】Program 3 : Complicated Expression(网易游戏笔试题)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
时间限制:50000ms
单点时限:5000ms
内存限制:256MB
描述
在lisp语言中，表达式都用前缀法表示，例如，1 + 2 在lisp中使用(+ 1 2)来表示，其中，表达式的括号是必需的。Bob 想实现一种类 lisp 的脚本语言，这个语言中的表达式是这样定义的：
1、每个表达式的形式都是 ( operator arg_1 arg_2 ... )，即由左括号，运算符，运算数，和右括号组成。
2、运算符包括三种，分别是'+', '-', '*'。
3、运算符如果可以接受一个运算数，就称为一元运算符，如果可以接受两个运算数，就称为二元运算符，如果可以接受三个及以上运算数，就称为多元运算符。
+ 可以是一元，二元，乃至多元运算符。
(+ 9) 表示正整数9；
(+ 1 2) 代表 1 + 2；
(+ 1 2 3 4) 代表 1, 2, 3, 4 的连加和。
- 可以是一元或者二元运算符。
(- 9) 表示整数-9；
(- 5 4) 代表 5 - 4。
* 可以是二元运算符或者多元运算符。
(* 2 3) 代表 2 * 3；
(* 1 2 3 4) 代表 1 * 2 * 3 * 4。
4、运算数可以是一个正整数，或者0，还可以是另外一个表达式，例如
(+ (* 2 3) 1) 也是一个合法的表达式，代表了 2 * 3 + 1
5、运算符与运算数之间，运算数与运算数相互之间都以空格进行分隔。在不产生歧义的情况下，空格也可以省略。例如，
(+ 2 3) 和 ( +2 3) 都被认为是合法的输入，且有相同的意义，代表 2 + 3。(+ 23)也是一个合法的输入，但其代表的是正整数23。
输入
输入由多行组成，第一行包含一个正整数T(T <= 5000)。代表共包含T组测试数据。
接下来会有T行输入。每一行包含一个表达式。这个表达式可能是一个合法的表达式，也可能是不合法的表达式。
每行数据所包含的字符数，不超过1000000。
输入数据中的数字全部是十进制正整数或者0，而且正整数的值不会大于65535。
输入中的表达式只包含三种不同类型的错误，除此之外的情况，都不必考虑。
第一类错误，括号不匹配，例如
(+ (* 2 3) 1)) 多了一个右括号;
+ 2 3 缺少括号等。
第二类错误，运算符缺失，例如
(2 3) 没有运算符。
第三类错误，运算符与数字不匹配，例如
(- 1 2 3)，由于 - 只能接受最多两个算数，所以这也是一个不合法的表达式。
输出
对于合法的表达式，请输出表达式的值，对于不合法的表达式，请输出“invalid expression”。
可以假设最后的结果不超过32位整数的表示范围，但不保证在某些情况下，计算的中间值全部不超过32位整数的表示范围。
样例输入
5 (+ 1 (* 2 3))) (2 3) (- 3 2 1) (+ (+ 1 2) (* 2 3) (- 2 1)) (- 2)
样例输出
invalid expression
invalid expression
invalid expression
10
-2
invalid expression
invalid expression
10
-2
代码：
#include "stdafx.h"
#include <string>
#include <stdio.h>
#include <stack>
#include <iostream>
using namespace std;
int pow( int n)
{
int result = 1 ;
if (n == 0 )
{
return 1 ;
}
else {
for ( int i = 0 ; i < n; ++i )
{
result *= 10 ;
}
}
return result ;
}
int main()
{
int n;
string str;
stack<char > temp;
cin >> n ;
cin.ignore (0x7fffffff, '\n');
while (n--)
{
stack <int> num;
bool hasnum = false;
getline (cin, str);
bool isexit = false;
if ( str[0 ] != '(' )
{
cout << "invalid expression" << endl;
}
else
{
for ( int i = 0 ; i < str.length (); ++ i)
{
if ( str[i ] == '(' )
{
if ( str[i + 1 ] != '+' && str[i + 1 ] != '-' && str[i + 1 ] != '*' ) {
cout << "invalid expression" << endl;
isexit = true ;
break;
}
else {
temp .push( str[i ]);
}
}
else if (str[i ] == ')' ) {
int multi = 0;
int count = 0;
int cnt = 0 ;
int subcount = 0;
bool isfirst = false;
int first = 0;
bool isback = false;
if ( temp.empty ())
{
cout << "invalid expression" << endl;
isexit = true ;
break;
}
while ( temp.size () > 0 && temp.top () != '(' )
{
if ( temp.top () >= '0' && temp.top () <= '9' )
{
hasnum = true ;
multi += ( temp.top () - '0' ) * pow(count );
count ++;
temp .pop();
}
else if (temp.top () == '#' )
{
if ( hasnum == true)
{
num .push( multi);
hasnum = false ;
multi = 0 ;
count = 0 ;
if ( isfirst == false)
{
first = num. top();
isfirst = true ;
}
}
temp .pop();
}
else if (temp.top () == '+' )
{
int result = 0;
if ( hasnum == true)
{
num .push( multi);
hasnum = false ;
multi = 0 ;
count = 0 ;
}
while ( num.top () != first && num .size() > 1)
{
result += num. top();
num .pop();
}
result += num. top();
num .pop();
num .push( result);
temp .pop();
isback = true ;
}
else if (temp.top () == '-' )
{
int result = 0;
if ( hasnum == true)
{
num .push( multi);
hasnum = false ;
multi = 0 ;
count = 0 ;
}
int a[ 2] = { 0 };
while ( num.top () != first && num .size() > 1)
{
subcount ++;
a [0] = num.top ();
num .pop();
}
if ( subcount == 1)
{
a [1] = num.top ();
num .pop();
if ( a[1] == first)
{
result = a[ 0] - a[ 1];
}
else
result = a[ 1] - a[ 0];
}
else if (subcount >= 2) {
cout << "invalid expression" << endl;
isexit = true ;
break;
}
else {
result = 0 - num.top ();
num .pop();
}
subcount = 0 ;
num .push( result);
temp .pop();
isback = true ;
}
else if (temp.top () == '*' )
{
int result = 1;
if ( hasnum == true)
{
num .push( multi);
hasnum = false ;
multi = 0 ;
count = 0 ;
}
if ( num.size ())
{
while ( num.top () != first&& num .size() > 1)
{
result *= num. top();
num .pop();
}
result *= num. top();
num .pop();
}
else
{
cout << "invalid expression" << endl;
isexit = true ;
break;
}
subcount = 0 ;
num .push( result);
temp .pop();
isback = true ;
}
}
temp .pop();
}
else {
if ( str[i ] == ' ' )
{
temp .push( '#');
}
else
temp .push( str[i ]);
}
}
}
if (! isexit)
{
if (! temp.empty ())
{
cout << "invalid expression" << endl;
break;
}
if ( num.size () == 1 )
{
cout << num. top() << endl;
}
}
}
return 0;
}
