NowCoder从小就喜欢数学,喜欢在笔记里记录很多表达式。它觉得现在的表达式写法很麻烦,为了提高运算符优先级,不得不添加很多括号,不小心漏了一个右括号的话差之毫厘谬之千里。
因此他改用前缀表达式,例如`(2 + 3) * 4`写成`* + 2 3 4`,这样就能避免使用括号了。这样的表达式书写简单,但计算却不够直观。请你写一个程序帮他计算这些前缀表达式吧。
输入包含多组数据,每组数据包含两行。
第一行为正整数n(3≤n≤50),紧接着第二行包含n个由数值和运算符组成的列表。
“+-*/”分别为加减乘除四则运算,其中除法为整除,即“5/3=1”。
对应每一组数据,输出它们的运算结果。
3 + 2 3 5 * + 2 2 3 5 * 2 + 2 3
5 12 10
def calc(arr):
for i,v in enumerate(arr):
if v in ["+","-","*","/"]:
if arr[i+1].isnumeric() and arr[i+2].isnumeric():
return calc(arr[:i]+[str(int(eval(arr[i+1]+v+arr[i+2])))]+arr[i+3:])
return arr[0]
while True:
try:
a,b=input(),input().split()
print(calc(b))
except:
break
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); String[] arr = new String[n]; Stack<Integer> stack = new Stack<>(); for (int i = 0; i < n; i ++ ) arr[i] = sc.next(); for (int i = n - 1; i >= 0; i -- ) { if(arr[i].equals("+")) stack.push(stack.pop() + stack.pop()); else if(arr[i].equals("-")) stack.push(stack.pop() - stack.pop()); else if(arr[i].equals("*")) stack.push(stack.pop() * stack.pop()); else if(arr[i].equals("/")) stack.push(stack.pop() / stack.pop()); else stack.push(Integer.parseInt(arr[i])); } System.out.println(stack.pop()); } } }
#include<iostream> #include<vector> #include<string> #include<algorithm> #include<functional> #include <map> #include <set> #include <unordered_set> #include <unordered_map> #include <exception> #include <iomanip> #include <memory> #include <sstream> #include <list> using namespace std; int main(int argc, char** argv) { //freopen("in.txt", "r", stdin); int n; while (cin >> n) { vector<string> pre; string s; for (int i = 0; i < n; ++i) { cin >> s; pre.emplace_back(s); } while (pre.size() > 1) { for (int i = pre.size() - 1; i >= 0;--i) { string op = pre[i]; if (op == "+" || op == "-" || op == "*" || op == "/") { int x = stoi(pre[i + 1]), y = stoi(pre[i + 2]); switch (op[0]) { case '+': x += y; break; case '-': x -= y; break; case '*': x *= y; break; case '/': x /= y; break; default:break; } pre[i] = to_string(x); pre.erase(pre.begin() + i + 1, pre.begin() + i + 3); break; } } } cout << pre[0] << endl; } return 0; }
//利用堆栈;从右向左扫面输入的字符串:如果是数字的话,数字进栈; //符号的话,弹出栈顶的两个元素做运算,运算结果进栈 #include<iostream> #include<stack> #include<string> #include<vector> using namespace std; int main() { int n,i,a,b,t; stack<int> ret; while(cin>>n) { if(n==0) continue; vector<string> v(n); i=0; while(i<n) { cin>>v[i++]; } for(i=n-1; i>=0; i--) { if(v[i].compare("+")==0) { a=ret.top(); ret.pop(); b=ret.top(); ret.pop(); ret.push(a+b); } else if(v[i].compare("-")==0) { a=ret.top(); ret.pop(); b=ret.top(); ret.pop(); ret.push(a-b); } else if(v[i].compare("*")==0) { a=ret.top(); ret.pop(); b=ret.top(); ret.pop(); ret.push(a*b); } else if(v[i].compare("/")==0) { a=ret.top(); ret.pop(); b=ret.top(); ret.pop(); ret.push(a/b); } else { // cout<<v[i]<<endl; ret.push(atoi(v[i].c_str())); } } cout<<ret.top()<<endl; v.clear(); while(!ret.empty()){ ret.pop(); } } return 0; }
import sys while True: try: # 从右向左扫描字符串,遇到操作符比较操作符合栈顶元素的优先级, n = int(input()) s = input() L = s.split() L = L[::-1] operations = ["+", "-", "*", "/"] stack1 = [] stack2 = [] for i in L: if i in operations: x = stack2.pop() y = stack2.pop() z = eval(x + i + y) stack2.append(str(z)) else: stack2.append(i) print(stack2.pop()) #print(str(int(stack2.pop()))) except: break
// write your code here cpp #include<cstdio> (802)#include<stack> #include<cstring> (803)#include<cctype> using namespace std; int main(){ char str[60][20]; int n; while(scanf("%d",&n)!=EOF){ stack<int> s; for(int i=0;i<n;++i){ scanf("%s",str[i]); } for(int i=n-1;i>=0;--i){ if(isdigit(str[i][0])){ int sum=0; for(int j=0;j<strlen(str[i]);++j){ sum=sum*10+str[i][j]-'0'; } s.push(sum); }else{ int a=s.top(); s.pop(); int b=s.top(); s.pop(); int sum; if(str[i][0]=='+') sum=a+b; else if(str[i][0]=='-') sum=a-b; else if(str[i][0]=='*') sum=a*b; else sum=a/b; s.push(sum); } } printf("%d\n",s.top()); } }
import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); Stack<Node> nodeStack = new Stack<>(); Node root = null; for (int i = 0; i < n; i++) { if (i == 0) { Node newNode = new Node(sc.next()); nodeStack.push(newNode); root = newNode; } else { Node pNode = nodeStack.peek(); Node newNode = new Node(sc.next()); if (pNode.lchild == null) { pNode.lchild = newNode; } else if (pNode.rchild == null) { pNode.rchild = newNode; nodeStack.pop(); } if (!newNode.isLeaf) { nodeStack.push(newNode); } } } System.out.println(root.getValue()); } sc.close(); } static class Node { Node lchild, rchild; String val; int intVal; boolean isLeaf = true; public Node(String val) { this.val = val; try { this.intVal = Integer.parseInt(this.val); } catch (Exception e) { isLeaf = false; } } int getValue() { if (isLeaf) { return intVal; } switch (val) { case "+": return lchild.getValue() + rchild.getValue(); case "-": return lchild.getValue() - rchild.getValue(); case "*": return lchild.getValue() * rchild.getValue(); default: return lchild.getValue() / rchild.getValue(); } } } }构建二叉树,叶子节点是数字,非叶子节点是符号,这样子输入实际上是一个扩展二叉树序列,最后从根节点开始计算表达式的值
#include <bits/stdc++.h> using namespace std; long long atoi(string s) { long long res = 0; for (int i = 0; i < s.size(); ++i) { res = res * 10 + s[i] - '0'; } return res; } int main() { int n; while (cin >> n) { string s[50]; stack<long long> num; for (int i = 0; i < n; ++i) { cin >> s[i]; } for (int i = n - 1; i >= 0; --i) if (s[i] == "+" || s[i] == "-" || s[i] == "*" || s[i] == "/") { long long left = num.top(); num.pop(); long long right = num.top(); num.pop(); if (s[i] == "+") left += right; else if (s[i] == "-") left -= right; else if (s[i] == "*") left *= right; else left /= right; num.push(left); } else { num.push(atoi(s[i])); } cout << num.top() << endl; } return 0; }
import java.util.Scanner; import java.util.Stack; public class Main { private static Scanner scan = new Scanner(System.in); public static void main(String[] args) { while(scan.hasNext()){ Stack<String> stackStr = new Stack<>();//暂存所有字符 Stack<Integer> stack = new Stack<>();//暂存运算数字 int n = Integer.parseInt(scan.next()); for(int i = 1; i <= n; ++i) stackStr.push(scan.next()); for(int i = 1; i <= n; ++i){ String str = stackStr.pop(); //判断是否是数字 if (Character.isDigit(str.charAt(0))) { stack.push(Integer.parseInt(str)); } else { char c = str.charAt(0); int a = stack.pop(); int b = stack.pop(); switch (c) { case '+': stack.push(a+b); break; case '-': stack.push(a-b); break; case '*': stack.push(a*b); break; case '/': stack.push(a/b); break; } } } System.out.println(stack.pop()); } } }
这个代码输入哪个“前缀表达式”会发生溢出?
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <functional> #include <algorithm> #include <numeric> #include <stack> #include <queue> #include <vector> #include <string> #include <sstream> using namespace std; void myPush (stack<char> &st, char bas); char cal (int one, int two, char opchar); char cal (int one, int two, char opchar) { switch (opchar) { case '+': return one + two + 48; case '-': return one - two + 48; case '*': return one * two + 48; case '/': { if (0 == two) { return 0; } return one / two + 48; } default: { cout << "输入有误" << endl; return 0; } } } void myPush (stack<char> &st, char bas) { if (st.empty () || st.top () < '0' || st.top () > '9' || bas < '0' || bas > '9') { st.push (bas); } else { int one = st.top () - 48; int two = bas - 48; st.pop (); char opchar = st.top (); st.pop (); char ret = cal (one, two, opchar); myPush (st, ret); } } int main () { int n; while (scanf ("%d", &n) != EOF) { char bas; stack<char> st; for (int x = 0; x < n; x++) { cin >> bas; myPush (st, bas); } cout << st.top() - 48 << endl; } return 0; }
import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { try(Scanner scanner = new Scanner(System.in)){ while(scanner.hasNext()){ int n = Integer.parseInt(scanner.next()); Stack<String> inStack = new Stack<>(); Stack<Integer> stack = new Stack<>(); for(int i=0;i<n;i++){ String input = scanner.next(); inStack.push(input); } while(inStack.size()>0){ String input = inStack.pop(); char c = input.charAt(0); if(c>='0'&&c<='9'){ stack.push(Integer.parseInt(input)); }else{ int a = stack.pop(); int b = stack.pop(); switch(c){ case '+':stack.push(a+b);break; case '-':stack.push(a-b);break; case '*':stack.push(a*b);break; case '/':stack.push(a/b);break; } } } System.out.println(stack.pop()); } } } }