首页 > 试题广场 >

表达式求值

[编程题]表达式求值
  • 热度指数:117694 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定一个字符串描述的算术表达式,计算出结果值。

输入字符串长度不超过 100 ,合法的字符包括 +, -, *, /, (, )0-9

数据范围:运算过程中和最终结果均满足 ,即只进行整型运算,确保输入的表达式合法

输入描述:

输入算术表达式



输出描述:

计算出结果值

示例1

输入

400+5

输出

405
package main

import "fmt"

func main(){
    var expression string
    fmt.Scanln(&expression)
    fmt.Println(calculate(expression))
}

func calculate(s string)int{
    stack := []int{} // 一个栈存储所有计算过的数字
    var sign byte = '+'
    var num int
    for i := 0; i < len(s); i ++{
        c := s[i]
        if c == ' '{
            continue
        }else if isDigit(c){
            num = num * 10 + int(c - '0')
        }else if c == '('{
            // 向后找到配对的右括号
            j := i + 1
            count := 1 // 记录出现过的左括号数量
            for count > 0{
                if s[j] == ')'{
                    count --
                }else if s[j] == '('{
                    count ++
                }
                j ++
            }
            // 找出括号范围后递归求内部表达式的结果
            num = calculate(s[i+1:j-1])
            i = j - 1
        }else if c == ')'{
            continue
        }
        if !isDigit(c) || i == len(s)-1{
            if sign == '+'{
                stack = append(stack, num)
            }else if sign == '-'{
                stack = append(stack, -num)
            }else if sign == '*'{
                stack[len(stack)-1] *= num
            }else if sign == '/'{
                stack[len(stack)-1] /= num
            }
            sign = c
            num = 0
        } 
    }
    ans := 0
    for _, n := range stack{
        ans += n
    }
    return ans
}

func isDigit(b byte)bool{
    if b >= '0' && b <= '9'{
        return true
    }
    return false
}

发表于 2022-05-21 23:51:30 回复(0)
还要处理负数我是没想到的,所以要加个预处理补0,好在样例不多,所以是纯纯的面向样例编程
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Iterator;

public class Main{
    public static int isp(char c){
        int k;
        switch(c){
            case '#': k = 0; break;
            case '(': k = 1; break;
            case '+': k = 3; break;
            case '-': k = 3; break;
            case '*': k = 5; break;
            case '/': k = 5; break;
            case ')': k = 6; break;
            default: k = -1;
        }
        return k;
    }
    
    public static int icp(char c){
        int k;
        switch(c){
            case '#': k = 0; break;
            case '(': k = 6; break;
            case '+': k = 2; break;
            case '-': k = 2; break;
            case '*': k = 4; break;
            case '/': k = 4; break;
            case ')': k = 1; break;
            default: k = -1;
        }
        return k;
    }
    
    public static LinkedList<String> getPostfix(StringBuilder inp){
        LinkedList<Character> stack = new LinkedList<>();
        LinkedList<String> queue = new LinkedList<>(); //存储后缀表达式
        
        stack.addLast('#');
        inp.append("#");
        
        for(int i = 0; i<inp.length(); i++){
//             Iterator iter = queue.iterator();
//             System.out.print("epoch " + i + ":  ");
//             while(iter.hasNext()){
//                 System.out.print(iter.next() + " ");
//             } 
//             System.out.println();
            
            Integer num = new Integer(0);
            boolean isDigitFlag = false;
            
            while(i<inp.length() && Character.isDigit(inp.charAt(i))){
                isDigitFlag = true;
                num = num*10 + (inp.charAt(i) - '0');
                i++;
            }
//             System.out.println("content : " + num);
            if(isDigitFlag)queue.addLast(num.toString());
            
            Character tmp1 = inp.charAt(i); // 栈外
            Character tmp2 = stack.getLast(); // 栈内
                    
//             if(icp(tmp1)<0) queue.addLast(tmp1.toString());
            if(icp(tmp1) > isp(tmp2)) stack.addLast(tmp1);
            else if(icp(tmp1) < isp(tmp2)){
                Character tmp = stack.removeLast();
                queue.addLast(tmp.toString());
                i--;
            }
            else stack.removeLast();
        }
        return queue;
    }
    
    public static int calPostfix(LinkedList<String> queue){
        LinkedList<Integer> stack = new LinkedList<>();
        while(!queue.isEmpty()){
            String tmp = queue.removeFirst();
            try{
                int a = Integer.parseInt(tmp);
                stack.addLast(a);
            }catch(NumberFormatException e){
                int b = stack.removeLast();
                int a = stack.removeLast();
                switch(tmp){
                    case "+":stack.addLast(a+b); break;
                    case "-":stack.addLast(a-b); break;
                    case "*":stack.addLast(a*b); break;
                    case "/":stack.addLast(a/b); break;
                    default: break;
                }
            }
        }
        return stack.removeLast();
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String res = new String(sc.nextLine());  
        res = res.replaceAll("^-","0-");
        res = res.replaceAll("[(]-","(0-");
        StringBuilder inp = new StringBuilder(res);  

        
        LinkedList postFix = getPostfix(inp);
        System.out.println(calPostfix(postFix));
    }
}


发表于 2022-04-21 00:11:11 回复(0)
这是一道简单题!!!!!!!!!!!!!!
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            String input = scan.nextLine();
            System.out.println(sub(input));
        }
    }
    public static int sub(String input) {
        int res = 0;
        int number = 0;
        Stack<Integer> sum = new Stack<>();
        char sign = '+';
        for (int i = 0; i < input.length(); i++) {
            char item = input.charAt(i);
            if (item == ' ') {
                continue;
            }
            if (Character.isDigit(item)) {
                number = number * 10 + item - '0';
            } else {
                if (item == '(') {
                    int count = 1;
                    int j = i + 1;
                    while (count > 0) {
                        char ch = input.charAt(j);
                        if (ch == '(') {
                            count++;
                        } else if (ch == ')') {
                            count--;
                        }
                        j++;
                    }
                    number = sub(input.substring(i+1, j - 1));
                    i = j - 1;
                }
                // = - * /
                    caculate(number, sign, sum);
                    sign = item;
                    number = 0;
                
            }
        }
        if (number != 0) {
            caculate(number, sign, sum);
        }
//         System.out.println();
        while (!sum.isEmpty()) {
            int each = sum.pop();
//             System.out.print(each+".");
            res += each;
        }
        return res;
    }
    public static void caculate(int number, char sign, Stack<Integer> sum) {
//         System.out.print(number + "&" + sign + "~~");
        if (sign == '+') {
            sum.push(number);
        } else if (sign == '-') {
            sum.push(-1 * number);
        } else if (sign == '*') {
//             System.out.print(sum.peek()+"*" + number);
            int res = sum.pop() * number;
//             System.out.print("=" + res);
            sum.push(res);
        } else if (sign == '/') {
            sum.push(sum.pop() / number);
        }
    }
}


发表于 2022-03-05 14:09:22 回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
import java.util.regex.Pattern;

/**  * 字符串预处理  * 中缀表达式转后缀表达式  * 后缀表达式计算  */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        List<String> ls = transform(input);
        Stack<String> my = reverse(doTrans(ls));
        int result = doCalc(my);
        System.out.println(result);
    }

    public static Stack<String> reverse(Stack<String> my) {
        Stack<String> stack = new Stack();
        while (!my.empty()) {
            stack.push(my.pop());
        }
        return stack;
    }

    public static int doCalc(Stack<String> my) {
        Stack<Integer> s1 = new Stack();  // 临时存储
        while (!my.empty()) {
            String ch = my.pop();
            switch (ch) {
                case "+":
                    int b1 = s1.pop();
                    int a1 = s1.pop();
                    s1.push(a1 + b1);
                    break;
                case "-":
                    int b2 = s1.pop();
                    int a2 = s1.pop();
                    s1.push(a2 - b2);
                    break;
                case "*":
                    int b3 = s1.pop();
                    int a3 = s1.pop();
                    s1.push(a3 * b3);
                    break;
                case "/":
                    int b4 = s1.pop();
                    int a4 = s1.pop();
                    s1.push(a4 / b4);
                    break;
                default:
                    s1.push(Integer.parseInt(ch));    //如果当前的字符数字, 则直接压入s1
                    break;
            }
        }
        return s1.pop();
    }


    /**
     * 转换中缀表达式为后缀表达式
     *
     * @param ls String
     * @return Stack
     */
    public static Stack<String> doTrans(List<String> ls){
        Stack<String> s1 = new Stack();
        Stack<String> s2 = new Stack();
        if (!ls.isEmpty()) {
            for(String ch : ls) {
                switch (ch) {
                    case "+":
                    case "-":
                        compAndPush(ch, 1, s1, s2);
                        break;
                    case "*":
                    case "/":
                        compAndPush(ch, 2, s1, s2);
                        break;
                    case "(":
                        s1.push(ch); //如果当前字符是'(',则将其入栈
                        break;
                    case ")":
                        gotParen(ch, s1, s2);
                        break;
                    default:
                        //1、如果当前解析的字符是操作数,则直接压入s2
                        s2.push(ch);
                        break;
                }
            }

            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }

        return s2;
    }

    public static void compAndPush(String opThis, int pre1, Stack<String> s1, Stack<String> s2){
        while (!s1.isEmpty()) {
            String opTop = s1.peek();
            if ("(".equals(opTop)) {
                s1.push(opThis);
                break; // 如果栈顶是'(',直接将操作符压入s1,跳出循环
            } else {
                int pre2 = getPriority(opTop); // 获取优先级
                if (pre2 < pre1) {
                    s1.push(opThis);
                    break; // 如果当前运算符比s1栈顶运算符优先级高,则将运算符压入s1,跳出循环
                } else {
                    s2.push(s1.pop()); // 如果当前运算符比s1栈顶运算符优先级低或等于,则将运算符压入s1,结合while继续循环
                }
            }
        }
        if (s1.isEmpty()) {
            s1.push(opThis); // 如果s1为空直接压入s1
        }
    }

    public static int getPriority(String opTop) {
        if ("+".equals(opTop) || "-".equals(opTop)) {
            return 1;
        } else {
            return 2;
        }
    }

    public static void gotParen(String ch, Stack<String> s1, Stack<String> s2){
        while(!s1.isEmpty()){
            String chx = s1.pop();
            if("(".equals(chx)){
                break;
            }else{
                s2.push(chx);
            }
        }
    }

    public static List<String> transform(String str) {
        List<String> ls = new ArrayList<>();
        String[] strLs = str.split("");
        StringBuffer sb = new StringBuffer();
        for (int i = 0 ; i < strLs.length; i++) {
            String s = strLs[i];
            String pattern = "[()*+/]";
            String pattern1 = "[(*+/]";
            if (Pattern.matches(pattern, s)) { //运算符号()*+/
                if (!sb.toString().isEmpty()) {
                    ls.add(sb.toString());
                    sb = new StringBuffer();
                }
                ls.add(s);
            } else {
                if ("-".equals(s)) {
                    if (i == 0 || Pattern.matches(pattern1, strLs[i - 1])) { // 负数
                        sb.append("-");
                    } else {   // 减号
                        if (!sb.toString().isEmpty()) {
                            ls.add(sb.toString());
                            sb = new StringBuffer();
                        }
                        ls.add(s);
                    }
                } else {  // 数字
                    sb.append(s);
                }
            }

        }
        if (!sb.toString().isEmpty()) {
            ls.add(sb.toString());
        }
        return ls;
    }
}
发表于 2021-08-14 14:32:52 回复(0)
四则运算表达式,计算表达式结果:
1.将中缀表达式转换为后缀表达式。
A.将[ ] { }替换为( )
B.将负数前面插入0,如果首个字符为负数则插入0,后面的字符当前为负号且前一个字符不为数字和)则插入一个。
C.字符串切割时,注意多位字符的数字情况, 从第一个字符用isdigit判定,连续判定到一个数字的最后一位,并截取。保存字符

串时用逗号分隔。得到后缀表达式。
2.通过逗号分隔后缀表达式,用栈帮助计算数值。

#include <iostream>
#include <stack>
using namespace std;


string expresstrancela( string mid_express)
{
	//中缀表达式转后缀表达式
	string post_express;
	stack<char> oprerator_stack;
	oprerator_stack.push('#');

	//将表达式中的大括号中括号替换为小括号
	for (int i=0;i<mid_express.size();i++)
	{
		char c = mid_express[i];
		if ((c=='[')||(c=='{'))
		{
			mid_express[i] = '(';
		}
		if ((c==']')||(c=='}'))
		{
			mid_express[i] = ')';
		}
	}

	if (*mid_express.begin() == '-')
	{
		mid_express.insert(mid_express.begin(),0);
	}

	for (auto m = mid_express.begin()+1; m!= mid_express.end();m++ )
	{
		if (((*m == '-')&& ((*(m-1) < '0') || *(m-1) > '9')) && (*(m-1) != ')'))
		{
			mid_express.insert(m,'0');
		}
	}

	for (int i=0;i<mid_express.size();i++)
	{
		char c = mid_express[i];
		if (isdigit(mid_express[i]))
		{
			if (((i+1)<mid_express.size())&&(isdigit(mid_express[i+1])))
			{
				post_express.push_back(mid_express[i++]);
				post_express.push_back(mid_express[i]);
				post_express.push_back(',');
			}
			else
			{
				post_express.push_back(mid_express[i]);
				post_express.push_back(',');
			}
			continue;
		}

		if (c == '(')
		{
		    oprerator_stack.push(c);
			continue;
		}

		if (c == ')')
		{			
			while('(' != oprerator_stack.top())
			{
				char c_temp = oprerator_stack.top();
				post_express.push_back(c_temp);
				post_express.push_back(',');
				oprerator_stack.pop();
			}
			oprerator_stack.pop();
			continue;
		}

		if (((c =='*')||(c =='/'))&&(('+'== oprerator_stack.top())||('-'== oprerator_stack.top())))
		{
			oprerator_stack.push(c);
			continue;
		}
		else
		{
			if ((c =='+')||(c =='-'))
			{
				while((oprerator_stack.top() == '+')||(oprerator_stack.top() == '-')||(oprerator_stack.top() == '*')||(oprerator_stack.top() == '/'))
				{
					post_express.push_back(oprerator_stack.top());
					post_express.push_back(',');
					oprerator_stack.pop();
				}
				oprerator_stack.push(c);

			}

			if ((c =='*')||(c =='/'))
			{
				while((oprerator_stack.top() == '*')||(oprerator_stack.top() == '/'))
				{
					post_express.push_back(oprerator_stack.top());
					post_express.push_back(',');
					oprerator_stack.pop();
				}
				oprerator_stack.push(c);
			}
			continue;
		}

	}

	while(oprerator_stack.top()!='#')
	{
		post_express.push_back(oprerator_stack.top());
		post_express.push_back(',');
		oprerator_stack.pop();
	}
	
	return post_express;
}

int calpost_express(string post_express)
{
	stack<int> digtal_stack; 

	while( post_express.find(',') != string::npos )
	{
		int ipos = post_express.find(',');
		string sub = post_express.substr(0,ipos);
		post_express = post_express.substr(ipos+1,post_express.size()-ipos-1);

		//char c_temp = post_express[i];

		if ((string::npos == sub.find('+'))&&(string::npos == sub.find('-'))&&(string::npos == sub.find('*'))&&(string::npos == sub.find('/')))
		{
			int digtal = stoi(sub);
			digtal_stack.push(digtal);
		}

		if ("+" == sub)
		{
			int b = digtal_stack.top();
			digtal_stack.pop();
			int a = digtal_stack.top();
			digtal_stack.pop();

			int c = a + b;
			digtal_stack.push(c);
		}
		if ("-" == sub)
		{
			int b = digtal_stack.top();
			digtal_stack.pop();
			int a = digtal_stack.top();
			digtal_stack.pop();

			int c = a - b;
			digtal_stack.push(c);
		}
		if ("*" == sub)
		{
			int b = digtal_stack.top();
			digtal_stack.pop();
			int a = digtal_stack.top();
			digtal_stack.pop();

			int c = a * b;
			digtal_stack.push(c);
		}	
		if ("/" == sub)
		{
			int b = digtal_stack.top();
			digtal_stack.pop();
			int a = digtal_stack.top();
			digtal_stack.pop();

			int c = a / b;
			digtal_stack.push(c);
		}	
	}


	return digtal_stack.top();
}




int main() 
{
    string mid_express;
	cin>>mid_express;
	{
		//中缀转后缀
		string post_express = expresstrancela(mid_express);

		//计算后缀表达式值
		int value = calpost_express(post_express);

		cout << value << endl;
	}

	return 0;
}


发表于 2021-04-17 22:48:46 回复(0)
import re


prio = {
    "(": 0,
    "+": 1,
    "-": 1,
    "*": 2,
    "/": 2
}


def pre_process(s):
    return re.sub(r"(?<![0-9\)])(?=-[0-9\()])", r"0", s)


def pop_and_cal(op, data):
    o, b, a = op.pop(), data.pop(), data.pop()
    if o == "+":
        data.append(a+b)
    elif o == "-":
        data.append(a-b)
    elif o == "*":
        data.append(a*b)
    else:
        data.append(a/b)


def cal(exp):
    i, op, data = 0, [], []
    while i < len(exp):
        c = exp[i]
        if c.isdigit():
            j = i+1
            for j in range(i+1, len(exp)):
                if not exp[j].isdigit():
                    break
            data.append(int( exp[i:j] ))
            i = j
            continue
        elif not op:
            op.append(c)
        elif c == "(":
            op.append(c)
        elif c == ")":
            while op[-1] != "(":
                pop_and_cal(op, data)
            op.pop()
        else:
            while op and prio[op[-1]] >= prio[c]:
                pop_and_cal(op, data)
            op.append(c)
        i += 1
    while op:
        pop_and_cal(op, data)
    return data[0]


s = input()
exp = pre_process(s)
print(cal(exp))

发表于 2020-12-21 21:48:45 回复(1)
#include <iostream>
#include <stack>
#include <vector>
//需要使用中缀表达式转换成后缀表达式进行计算
//例如(5+6)*7 需要转换成 56+7*
using namespace std;

int main()
{
    string str;
    while(cin >> str)
    {
        stack<char> oper;//记录操作符
        vector<int> number;//记录数字的位数
        string s;//记录后缀表达式
        //中缀表达式转换后缀表达式
        for(int i = 0;i<str.size();i++)
        {
            if(str[i]>='0' && str[i] <='9')//当是数字的时候,将数字加入后缀中
            {
                int tmp = 0;
                while(i<str.size()&&str[i]>='0' && str[i] <='9')
                {
                    s+= str[i];
                    i++;
                    tmp++;
                }
                i--;
                number.push_back(tmp);
            }
            else if(str[i] == '-' || str[i] == '+')
            {
                //判断负数,例如(-5
                if(i >0 && str[i]=='-' && str[i-1] == '(' )
                {
                    s += '0';
                    number.push_back(1);
                }
                //如果 + - 的上一个操作符是+ - * / 那么可以直接加入后缀
                while(!oper.empty() && (oper.top() == '*' || oper.top() == '/' || oper.top() == '+'||oper.top() == '-'))
                {
                    s += oper.top();
                    oper.pop();
                }
                oper.push(str[i]);
            }
            else if(str[i] == '*' || str[i] == '/')
            {
                //如果 * / 的上一个操作符是 * / 那么可以直接加入后缀
                while(!oper.empty() && (oper.top() == '*' || oper.top() == '/'))
                {
                    s+=oper.top();
                    oper.pop();
                }
                oper.push(str[i]);
            }
            else if(str[i] == '(')
                oper.push(str[i]);
           //当前符号为右括号的时候,需要把之前的 不是左括号的操作符 放入后缀
            else if(str[i] == ')')
            {
                while(oper.top()!='(')
                {
                    s+=oper.top();
                    oper.pop();
                }
                oper.pop();
            }
            else 
            {
                cout<<"invalid operation"<<endl;
            }
        }
        while(!oper.empty())
        {
            s += oper.top();
            oper.pop();
        }
        //处理后缀表达式,并进行计算
        int tmp = 0;
        stack<int> res; 
        for(int i =0;i<s.size();i++)
        {
            //得到具体数字
            if(s[i] >= '0' && s[i] <='9')
            {
                int num = 0;
                while(number[tmp]--)
                    num = num*10 + (s[i++] - '0');
                i--;
                tmp++;
                res.push(num);
            }
            else{
                //进行计算,计算结果再入栈
                int num1 = res.top();
                res.pop();
                int num2 = res.top();
                res.pop();
                
                if(s[i] == '+')
                    res.push(num2+num1);
                else if(s[i] == '-')
                    res.push(num2-num1);
                else if(s[i] == '*')
                    res.push(num2*num1);
                else if(s[i] == '/')
                    res.push(num2/num1);
            }
        }
        cout<<res.top()<<endl;
    }
    return 0;
}

发表于 2020-07-17 12:16:43 回复(0)
#include <iostream>
#include <string>
#include <stack> 
using namespace std;

string cult_str(string str_in)
{
    for(int i = 1; i < str_in.length(); i++) { 
        if(str_in[i] == '*' || str_in[i] == '/') {
            int left = i - 1, right = i + 1;
            while(isdigit(str_in[left]) && left >= 0) {
                left--;
            }
            if((left == 0 && str_in[left] == '-') || (left >= 1 && str_in[left] == '-' && !isdigit(str_in[left - 1]))) {
                left--;
            }
            if(str_in[right] == '-') {
                right++;
            }
            while(isdigit(str_in[right]) && right <= str_in.length()) {
                right++;
            }
            string rest;
            switch(str_in[i]) {
                case '*':
                    rest = to_string(atoi(str_in.substr(left + 1, i - left - 1).c_str()) * atoi(str_in.substr(i + 1, right - i - 1).c_str()));
                    break;
                case '/':
                    rest = to_string(atoi(str_in.substr(left + 1, i - left - 1).c_str()) / atoi(str_in.substr(i + 1, right - i - 1).c_str()));
                    break;
                default:
                    break;
            }
            str_in.replace(left + 1, right - left - 1, rest);
            i = left + rest.length();
        }
    }
    for(int i = 1; i < str_in.length(); i++) {
        if(str_in[i] == '+' || str_in[i] == '-') {
            int left = i - 1, right = i + 1;
            while(isdigit(str_in[left]) && left >= 0) {
                left--;
            }
            if((left == 0 && str_in[left] == '-') || (left >= 1 && str_in[left] == '-' && !isdigit(str_in[left]))) {
                left--;
            }
            if(str_in[right] == '-') {
                right++;
            }
            while(isdigit(str_in[right]) && right <= str_in.length()) {
                right++;
            }
            string rest;
            switch(str_in[i]) {
                case '+':
                    rest = to_string(atoi(str_in.substr(left + 1, i - left - 1).c_str()) + atoi(str_in.substr(i + 1, right - i - 1).c_str()));
                    break;
                case '-':
                    rest = to_string(atoi(str_in.substr(left + 1, i - left - 1).c_str()) - atoi(str_in.substr(i + 1, right - i - 1).c_str()));
                    break;
                default:
                    break;
            }
            str_in.replace(left + 1, right - left - 1, rest);
            i = left + rest.length();
        }
    }
    return str_in;
}

int main() {
    string str_s;
    stack <char> char_s; 
    while(getline(cin, str_s)) { 
        for(int i = 0; i < str_s.length(); i++) {
            char_s.push(str_s[i]);
            if(char_s.top() == ')') {
                char_s.pop();
                string str_cut = "";
                while(char_s.top() != '(') {
                    str_cut.insert(0, 1, char_s.top());
                    char_s.pop();
                }
                char_s.pop();
                string str_out = cult_str(str_cut);
                for(int ii = 0; ii < str_out.length(); ii++) {
                    char_s.push(str_out[ii]);
                }
            }
        }
        string str_reslin = "", str_resl = "";
        while(!char_s.empty()){
            str_reslin.insert(0, 1, char_s.top());
            char_s.pop();  
        }
        str_resl = cult_str(str_reslin);
        cout << str_resl << endl;
    }
    system("pause");
    return 0;
}
//写的很难受
//用一个栈弹出括号 先算括号内
//四则运算 分负号出现在运算符左右 第一位是负数
//写的很别扭
发表于 2018-10-19 21:51:13 回复(0)
/*
 算法思想:算符优先法,考察栈的应用,用栈来实现算符优先法
 1.构建运算符的优先表priority_table[11][11]来存储算符的优先级
 2.初始化运算符栈optr用来存储运算符,***作数栈opnd存储***作数,初始时向optr压入#作为表达式的边界符号
 3.从表达式字符串中取字符,如果是数字则压入opnd,如果是***作符,则做以下***作:
 
 3.1如果新取的***作符优先级比optr栈顶的优先级高,则将其压入optr中
 3.2如果新取的***作符优先级比optr栈顶的优先级低,则先从optr中取出该运算符,
 再从opnd中连续取出两个***作数,进行运算后将其压入opnd中,新取运算符则压入optr中
 3.3如果新取的***作符优先级与optr栈顶的优先级一样,则从optr中连续弹出栈顶运算符
 4.重复3***作,直到optr为空,输出opnd中的栈顶元素即为结果
 */

#include <stack>
#include <iostream>
#include <string>
using namespace std;
//列顺序 +、-、*、/、(、)、[、]、{、}、# 11个符号
char priority_table[11][11]={
    {'>','>','<','<','<','>','<','>','<','>','>'},
    {'>','>','<','<','<','>','<','>','<','>','>'},
    {'>','>','>','>','<','>','<','>','<','>','>'},
    {'>','>','>','>','<','>','<','>','<','>','>'},
    {'<','<','<','<','<','=','<','x','<','x','x'},
    {'>','>','>','>','x','>','x','>','x','>','>'},
    {'<','<','<','<','<','x','<','=','<','x','x'},
    {'>','>','>','>','x','>','x','>','x','>','>'},
    {'<','<','<','<','<','x','<','x','<','=','x'},
    {'>','>','>','>','x','>','x','>','x','>','>'},
    {'<','<','<','<','<','x','<','x','<','x','='},
};

int findoptr_index(char ch)
{
    int index=0;
    switch(ch)
    {
        case '+':index=0;break;
        case '-':index=1;break;
        case '*':index=2;break;
        case '/':index=3;break;
        case '(':index=4;break;
        case ')':index=5;break;
        case '[':index=6;break;
        case ']':index=7;break;
        case '{':index=8;break;
        case '}':index=9;break;
        case '#':index=10;break;
    }
    return index;
}

int docalc(int a,int b,char op)
{
    int result=0;
    switch(op)
    {
        case '+':result=a+b;break;
        case '-':result=a-b;break;
        case '*':result=a*b;break;
        case '/':result=a/b;break;
    }
    return result;
}

int calc(string str,char  priority_table[][11])
{
    str+='#';
    stack<int> opnd;       //***作数栈
    stack<char> optr;       //***作符栈
    optr.push('#');        //初始时,压入#作为运算表达式的结束标志
    int str_index=0;
    while(!optr.empty())
    {
        if(isdigit(str[str_index]))
        {
            string getnum="";
            getnum+=str[str_index++];
            while(isdigit(str[str_index]))
            {
                getnum+=str[str_index++];                
            }
            str_index--;
            opnd.push(atoi((char *)getnum.c_str()));
        }
        else
        {
            char op1=optr.top();
            int op1_index=findoptr_index(op1);
            int op2_index=findoptr_index(str[str_index]);
            switch(priority_table[op1_index][op2_index])
            {
                    
                case '<':optr.push(str[str_index]);break;
                case '=':optr.pop();break;
                case '>':int opnd1=opnd.top(); opnd.pop();
                    int opnd2=opnd.top(); opnd.pop();
                    char op=optr.top();optr.pop();
                    int temp=docalc(opnd2,opnd1,op);
                    opnd.push(temp);str_index--;break;
            }
        }
        str_index++;
    }
    int result=opnd.top();
    opnd.pop();
    return result;
}

int main()
{
    string str;
    while(cin>>str)
    {
        cout<<calc(str,priority_table)<<endl;
    }
}


发表于 2018-10-06 23:06:22 回复(0)
#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
stack <int> num;
stack <char> op;
string a; 

int opfirst(char temp)
{   int ans;
    switch(temp)
    {
        case '+': ans=1;break;
        case '-': ans=1;break;
        case '*': ans=2;break;
        case '/': ans=2;break;
        case '(': ans=0;break;
        case ')': ans=0;break;
    }
    return ans;
}

int opst(int a,int b, char k)
{
    int ans;
    switch(k)
    {
        case '+': ans=a+b;break;
        case '-': ans=a-b;break;
        case '*': ans=a*b;break;
        case '/': ans=a/b;break;
    }
    return ans;
}
int main()
{
    while(cin>>a)
    {
        for(int i=0;a[i]!=0;i++)
        {
            if(a[i]>='0'&&a[i]<='9')
            {
                int temp=0;
                while(a[i]>='0'&&a[i]<='9')
                {
                    temp=temp*10+a[i]-'0'; 
                    i+=1;
                } 
                num.push(temp);
                i-=1;
            }
            else if (a[i]==')')
            {
                while(op.top()!='('&&op.empty()==false)
                {
                    int a=num.top();
                    num.pop();
                    int b=num.top();
                    num.pop();
                    int ans=opst(b,a,op.top());
                    num.push(ans);
                    op.pop();
                }
                op.pop();
            }
            else if (a[i]=='(')
                {
                op.push(a[i]);
                }
            else
                 {
                while(op.empty()==false&& opfirst(a[i])<=opfirst(op.top()))
                  {
                      int a=num.top();
                    num.pop();
                    int b=num.top();
                    num.pop();
                    int ans=opst(b,a,op.top());
                    num.push(ans);
                    op.pop();
                  }
                  op.push(a[i]);
                 }
        }
        while(op.empty()==false)
        {
                    int a=num.top();
                    num.pop();
                    int b=num.top();
                    num.pop();
                    int ans=opst(b,a,op.top());
                    num.push(ans);
                    op.pop();
        }
        cout<<num.top()<<endl;
    }
}


发表于 2018-05-05 16:34:03 回复(0)
1、使用中缀表达式直接求值;
2、设定栈内与栈外两层优先级解决括号出入栈问题;
3、针对非法表达式做出判断,例如:左括号前面不能为数字和右括号;右括号前面不能为运算符;数字前面不能为右括号;当加减号为第一个字符或者加减号前面为运算符时,查看后一个字符,若为数字,当做正负号特殊处理,合法,其余情况出现两个运算符连续或者运算符开头均为不合法。
4、出入栈时完成括号匹配。
运行时间:3ms;
占用内存:432K;
代码如下:
#include<stdio.h>
#include<stack>
using namespace std;
stack<int> op;
stack<double> in;
bool GetOp(bool &flag,int &result,int &index,char str[]){
    if(index==0&&op.empty()){
        flag=true;
        result=0;
        return true;
    }
    if(str[index]==0){
        flag=true;
        result=0;
        return true;
    }
    if((str[index]=='+'||str[index]=='-')&&(index==0||(index>0&&(str[index-1]=='+'||str[index-1]=='-'||str[index-1]=='*'||str[index-1]=='/'||str[index-1]=='(')))&&(str[index+1]>='0'&&str[index+1]<='9')){
        if(str[index]=='-'){
            flag=false;
            index++;
            result=0;
            for(;str[index]<='9'&&str[index]>='0';index++){
                result*=10;
                result+=str[index]-'0';
            }
            result=0-result;
            return true;
        }
        else if(str[index]=='+')
            index++;
    }
    if(str[index]<='9'&&str[index]>='0'){
        if(index>0&&str[index-1]==')')
            return false;
        flag=false;
    }
    else{
        if(str[index]=='('){
            if(index>0&&((str[index-1]<='9'&&str[index-1]>='0')||str[index-1]==')'))
                return false;
            flag=true;
            result=5;
            index++;
            return true;
        }
        if(str[index]==')'){
            if(index==0||(index>0&&(str[index-1]=='+'||str[index-1]=='-'||str[index-1]=='*'||str[index-1]=='/')))
                return false;
            flag=true;
            result=6;
            index++;
            return true;
        }
        if(str[index]=='-'||str[index]=='+'||str[index]=='*'||str[index]=='/'){    
            if(index==0||(index>0&&(str[index-1]=='+'||str[index-1]=='-'||str[index-1]=='*'||str[index-1]=='/'||str[index-1]=='(')))
                return false;
            flag=true;
            if(str[index]=='+') result=1;
            else if(str[index]=='-') result=2;
            else if(str[index]=='*') result=3;
            else result=4;
            index++;
            return true;
        }
        else return false;
    }
    result=0;
    for(;str[index]<='9'&&str[index]>='0';index++){
        result*=10;
        result+=str[index]-'0';
    }
    return true;
} 
int main(){
    char str[110];
    int mat[7][2]={
        0,0,
        2,3,
        2,3,
        4,5,
        4,5,
        6,1,
        1,6,
    };
    while(gets(str)){
        bool flag,judge;
        int result,index=0;
        while(!op.empty()) op.pop();
        while(!in.empty()) in.pop();
        while(true){
            judge=GetOp(flag,result,index,str);
            if(judge==false) return 0;
            if(flag==false)
                in.push((double)result);
            else{
                double tmp;
                if(op.empty()||mat[result][0]>mat[op.top()][1])
                    op.push(result);
                else if(result==6){
                    while(op.top()!=0&&op.top()!=5){
                        int ret=op.top();
                        op.pop();
                        double b=in.top();
                        in.pop();
                        double a=in.top();
                        in.pop();
                        if(ret==1) tmp=a+b;
                        else if(ret==2) tmp=a-b;
                        else if(ret==3) tmp=a*b;
                        else tmp=a/b;
                        in.push(tmp);
                    }
                    if(op.top()==0)
                        return 0;
                    else
                        op.pop();
                }
                else{
                    while(mat[result][0]<mat[op.top()][1]){
                        int ret=op.top();
                        op.pop();
                        if(ret==5)
                            return 0;
                        double b=in.top();
                        in.pop();
                        double a=in.top();
                        in.pop();
                        if(ret==1) tmp=a+b;
                        else if(ret==2) tmp=a-b;
                        else if(ret==3) tmp=a*b;
                        else tmp=a/b;
                        in.push(tmp);
                    }
                    op.push(result);
                }
            }
            if(op.size()==2&&op.top()==0) break;
        }
        if(in.size()==1)
            printf("%.0lf",in.top());
        else
            return 0;
    }
    return 0;
}

发表于 2018-01-09 15:33:43 回复(0)
print(input)

python 一行。。。。
发表于 2016-08-28 05:41:22 回复(0)
print input()

发表于 2016-12-23 20:10:06 回复(0)

python 3 一行的解法:

print(eval(input()))
发表于 2017-09-06 14:58:09 回复(30)
好家伙,披着简单题外套的中等较难题
#include<iostream>
#include<vector>
using namespace std;

int cur=0;
int calculate(const string &s)
{
    vector<int> st;
    int num=0;
    char flag='+';
    while(cur<s.length())
    {
        if(s[cur]=='(')
        {
            cur++;
            num =calculate(s);
        }
        while(cur<s.size()&&s[cur]<='9'&&s[cur]>='0')
        {
            num =10*num +(s[cur]-'0');
            cur++;
        }
        if(flag=='+')    {st.push_back(num);}
        else if(flag=='-')    {st.push_back(-num);}
        else if(flag =='*'||flag=='/')
        {
            int t = st.back();
            st.pop_back();
            if(flag=='*')    {st.push_back(num*t);}
            else     {st.push_back(t/num);}
        }
        flag =s[cur];
        num=0;
        if(s[cur]==')')    {cur++;break;}
        cur++;
    }
    int sum =0;
    while(!st.empty())    {sum+=st.back();st.pop_back();}
    return sum;
}

int main()
{
    string s;
    while(cin>>s)
    {
        cout<<calculate(s)<<endl;
    }
    return 0;
}


发表于 2021-03-10 16:48:58 回复(0)
//我matlab也不是吃素的
fprintf('%d\n',eval(input('','s')));

发表于 2019-08-08 14:36:35 回复(4)
//思路:
//1.字符串预处理,针对可能出现的“{,},[,],-”等特殊情况进行替换,判断‘-’是负号还是减号,负号前面+0,转变成减法运算
//2.将中缀字符串转变为后缀字符串数组
//3.对后缀字符串数组进行求解
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<sstream>
using namespace std;
bool cmpPriority(char top,char cur)//比较当前字符与栈顶字符的优先级,若栈顶高,返回true
{
    if((top=='+' || top=='-') && (cur=='+' || cur=='-'))
        return true;
 if((top=='*' || top=='/') && (cur=='+' || cur=='-'|| top=='*' || top=='/'))
        return true;
    if(cur==')')
        return true;
    return false;
}
void preProcess(string &str)//对字符串进行预处理
{
    for(int i=0;i<str.size();++i)
    {
        if(str[i]=='{')//将‘{、}、[,]’替换成'()'
            str[i]='(';
        else if(str[i]=='}')
            str[i]=')';
        else if(str[i]=='[')
            str[i]='(';
        else if(str[i]==']')
            str[i]=')';
        else if(str[i]=='-')
        {
            if(i==0)//将'-'前面添加0转变成减法运算
                str.insert(0,1,'0');
            else if(str[i-1]=='(')
                str.insert(i,1,'0');
  }
 }
}
vector<string> mid2post(string &str)
{
    vector<string>vstr;
    stack<char>cstack;
    for(int i=0;i<str.size();++i)//扫描字符串
    {
        string temp="";
        if(str[i]>='0' && str[i]<='9')//若是数字
        {
            temp+=str[i];
            while(i+1<str.size() && str[i+1]>='0' && str[i+1]<='9')
            {
                temp+=str[i+1];//若是连续数字
                ++i;
   }
            vstr.push_back(temp);
  }
        else if(cstack.empty() || str[i]=='(')//若栈空或者字符为'('
            cstack.push(str[i]);
        else if(cmpPriority(cstack.top(),str[i]))//若栈顶元素优先级较高,栈顶元素出栈
        {
            if(str[i]==')')//若当前字符是右括号,栈中元素出栈,入字符串数组中,直到遇到'('
            {
                while(!cstack.empty() && cstack.top()!='(')
                {
                    temp+=cstack.top();
                    cstack.pop();
                    vstr.push_back(temp);
                    temp="";
                }
                cstack.pop();                    
            }
            else//栈中优先级高的元素出栈,入字符串数组,直到优先级低于当前字符
            {
                while(!cstack.empty() && cmpPriority(cstack.top(),str[i]))
                {
                    temp+=cstack.top();
                    cstack.pop();
                    vstr.push_back(temp);
                    temp="";
                }
                cstack.push(str[i]);
   }
        }
        else//当前字符优先级高于栈顶元素,直接入栈
         cstack.push(str[i]);
    }
    while(!cstack.empty())//栈中还存在运算符时,出栈,存入字符串数组
    {
        string temp="";
        temp+=cstack.top();
        cstack.pop();
        vstr.push_back(temp);
    }
    return vstr;
}
int calcPostExp(vector<string> & vstr)//对后缀表达式进行求值,主要是根据运算符取出两个操作数进行运算
{
    int num,op1,op2;
    stack<int>opstack;
    for(int i=0;i<vstr.size();++i)
    {
        string temp=vstr[i];
        if(temp[0]>='0' && temp[0]<='9')//如果当前字符串是数字,利用字符串流转化为int型
        {
            stringstream ss;
            ss<<temp;
            ss>>num;
            opstack.push(num);
        }
        else if(vstr[i]=="+")//若是操作符,取出两个操作数,进行运算,并将结果存入
        {
            op2=opstack.top();
            opstack.pop();
            op1=opstack.top();
            opstack.pop();
            opstack.push(op1+op2);
        }
        else if(vstr[i]=="-")
        {
            op2=opstack.top();
            opstack.pop();
            op1=opstack.top();
            opstack.pop();
            opstack.push(op1-op2);
        }
        else if(vstr[i]=="*")
        {
            op2=opstack.top();
            opstack.pop();
            op1=opstack.top();
            opstack.pop();
            opstack.push(op1*op2);
        }
        else if(vstr[i]=="/")
        {
            op2=opstack.top();
            opstack.pop();
            op1=opstack.top();
            opstack.pop();
            opstack.push(op1/op2);
        }
    }
    return opstack.top();//最终的栈顶元素就是求解的结果
}
void calcExp(string str)
{
    vector<string>vstr;
    preProcess(str);//对字符串进行预处理
    vstr=mid2post(str);//将中缀表达式转为后缀,保存在字符串数组中,方便下一步求解
    int res=calcPostExp(vstr);
    cout<<res<<endl;
}
int main()
{
    string str;
    while(getline(cin,str))
    {
        calcExp(str);
 }
    return 0;
}

发表于 2017-03-18 17:41:49 回复(4)
print(eval(input()))

发表于 2022-07-24 11:21:54 回复(0)
这是道简单题?我是沙笔,不想刷NM算法题了,好想上岸
发表于 2022-06-22 23:23:34 回复(7)
"""
题目说表达式合法性由做题者检查,并非程序检查,所以简单问题简单处理
while True:
    try:
        raw_str = input()
        valid_str = '+-*/()0123456789'
        if len(raw_str) > 100:
            print("Input exceeds maximum length")
        else:
            for i in raw_str:
                if i not in valid_str:
                    print("Input contains invalid string")
            print(eval(raw_str))    
    except:
        break
"""
print(eval(input()))

发表于 2021-07-15 21:57:57 回复(6)