描述
在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
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; }