首页 > 试题广场 >

现有一四则运算表达式，仅包含+-*()和0~9数字，请设计

[问答题]
现有一四则运算表达式，仅包含+-*/()和0~9数字，请设计一个算法，计算该表达式的值。 其中+-只作为运算符出现，不作为正负符号出现在表达式中。 
请完成calc的代码实现（C++或Java） 已有字符串和数字的转换方法（str2num, num2str）可直接调用，无须实现。
 C++: 
float str2num(char[] str)
{
    …
}
char[] num2str(float num)
{
    …
}
float calc(char[] exp)
{
    …
}
Java:
float str2num(String str)
{
    …
}
String num2str(float num)
{
    …
}
float calc(String exp)
{
    …
}
例如： 
输入“1+2*（3-4）” 
输出-1
添加回答
jfjfjfjfjdkjfdla头像 jfjfjfjfjdkjfdla
c++递归下降分析器的解法，语法规则：
expr   = term   [+- term]...
term   = factor [*/ factor]...
factor = number | (expr)

5块钱的代码，没有语法错误处理，零除检查，大数什么的：） 

float expr(char* s, int& pos);
float term(char* s, int& pos);
float factor(char* s, int& pos);
float number(char* s, int& pos);

float expr(char* s, int& pos) {
        float v = term(s, pos);
        while (s[pos] == '+' || s[pos] == '-') {
                if (s[pos++] == '+')
                        v += term(s, pos);
                else
                        v -= term(s, pos);
        }
        return v;
}

float term(char* s, int& pos) {
        float v = factor(s, pos);
        while (s[pos] == '*' || s[pos] == '/') {
                if (s[pos++] == '*')
                        v *= factor(s, pos);
                else
                        v /= factor(s, pos);
        }
        return v;
}

float factor(char* s, int& pos) {
        if (s[pos] == '(') {
                pos++;
                float v = expr(s, pos);
                pos++;
                return v;
        } else {
                return number(s, pos);
        }
}

float number(char* s, int& pos) {
        int n = 0;
        while (s[pos] >= '0' && s[pos] <= '9')
                n = n * 10 + s[pos++] - '0';
        return (float)n;
}

float calc(char[] exp) {
        int pos = 0;
        return expr(exp, pos);
}
发表于 2015-01-08 19:23:50 回复(1)
Unlimited_Blade_Works头像 Unlimited_Blade_Works 
//中缀表达式转后缀表达式
//一个符号栈，一个数栈
#include <bits/stdc++.h>
using namespace std;
#define type float

float str2num(char p[]);
int signPriority(char op);
type cal2(type a,type b,char op);
void calModel(stack<type>& numberStack,char op);
float calc(char str[]);

float str2num(char p[]){
    type number;
    sscanf(p,"%lf",&number);
    return number;
}

int signPriority(char op){
    if(op=='(') return 0;
    if((op=='+')||(op=='-')) return 1;
    if((op=='*')||(op=='/')) return 2;
}

type cal2(type a,type b,char op){
    switch(op){
        case '+': return a+b;
        case '-': return a-b;
        case '*': return a*b;
        case '/': return a/b;
    }
}

void calModel(stack<type>& numberStack,char op){
    type post = numberStack.top();
    numberStack.pop();
    type pre = numberStack.top();
    numberStack.pop();
    numberStack.push(cal2(pre,post,op));
}

float calc(char str[]){
    stack<char> signStack;
    stack<type> numberStack;
    int end = strlen(str);
    for(int i=0;i<end;){
        //跳过""
        while(i<end&&str[i]==' ') i++;
        //碰到符号
        if(!isdigit(str[i])) {
            char c = str[i++];
            if(c=='(') signStack.push(c);
            else if(c==')'){
                while((!signStack.empty())&&signStack.top()!='('){
                    calModel(numberStack,signStack.top());
                    signStack.pop();
                }
                //删去'('
                signStack.pop();
            }else{
                int curPriority = signPriority(c);
                while((!signStack.empty())&&(curPriority<=signPriority(signStack.top()))){
                    calModel(numberStack,signStack.top());
                    signStack.pop();
                }
                signStack.push(c);
            }
        }
        else {
            //数字是连续的
            string tmp = "";
            while (i < end && isdigit(str[i])) tmp += str[i++];
            char* p = (char*)tmp.data();
            numberStack.push(str2num(p));
        }
    }
    while(!signStack.empty()){
        calModel(numberStack,signStack.top());
        signStack.pop();
    }
    return numberStack.top();
}
编辑于 2019-07-19 15:53:57 回复(0)
Jimmy-yyj头像 Jimmy-yyj 
    private static void calc(String exp) {
        Stack<Integer> stackNum = new Stack<>();
        Stack<Character> operate = new Stack<>();
        for (int i = 0; i < exp.length(); i++) {
            char c = exp.charAt(i);
            int num = c - '0';
            if (num >= 0 && num <= 9) {
                stackNum.push(num);
            } else {
                switch (c) {
                    case '+':
                    case '-':
                        if (operate.size() > 0) {
                            Character peek = operate.peek();
                            while (operate.size() > 0 && peek == '*' || peek == '/') {
                                peek = operate.pop();
                                switch (peek) {
                                    case '*':
                                        stackNum.push((stackNum.pop() * stackNum.pop()));
                                        break;
                                    case '/':
                                        int num2 = stackNum.pop();
                                        if (num2 == 0) {
                                            System.out.println("除数不得为0！");
                                            return;
                                        }
                                        stackNum.push(stackNum.pop() / num2);
                                        break;
                                }
                            }
                        }
                        operate.push(c);
                        break;
                    case '*':
                    case '/':
                    case '(':
                        operate.push(c);
                        break;
                    case ')':
                        char pop;
                        while (operate.size() > 0 && (pop = operate.pop()) != '(') {
                            calcRun(stackNum, pop);
                        }
                        break;
                }
            }
        }
        while (operate.size() > 0 && stackNum.size() > 0) {
            calcRun(stackNum, operate.pop());
        }
        System.out.println(stackNum.pop());
    }
    private static void calcRun(Stack<Integer> stackNum, char pop) {
        Integer res = null;
        switch (pop) {
            case '+':
                res = stackNum.pop() + stackNum.pop();
                break;
            case '-':
                res = -(stackNum.pop() - stackNum.pop());
                break;
            case '*':
                res = stackNum.pop() * stackNum.pop();
                break;
            case '/':
                int t = stackNum.pop();
                if (t == 0) {
                    System.out.println("除数不得为0！");
                    return;
                }
                res = stackNum.pop() / t;
                break;
        }
        if (res != null) {
            stackNum.push(res);
        }
    }

编辑于 2016-09-22 23:12:47 回复(0)
徐庆伟头像 徐庆伟
package queue;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 使用逆波兰表达式进行运算
 * Created by xuqingwei on 15/7/3.
 */
public class Express {

    private String originalExp;
    private char[] chars;
    private Deque<Character> opStack = new ArrayDeque<>(); //运算符栈
    private Deque<Double> execStack = new ArrayDeque<>(); //运算逆波兰表达式栈
    private LinkedList<String> exps = new LinkedList<>(); //逆波兰表达式

    private Express() {
    }

    private Express(String exp) {
        this.originalExp = exp;
    }

    /**
     * 静态构造方法
     *
     * @param exp
     *
     * @return
     */
    public static Express create(String exp) {
        Express express = new Express(exp);
        express.init();
        return express;
    }

    /**
     * 中缀表达式转换成后缀表达式，即逆波兰表达式
     */
    private void init() {
        chars = originalExp.toCharArray();
        for (char ch : chars) {
            handle(ch);
        }
        handle('#');
    }

    private void handle(char ch) {
        if (ch == ' ') {
            return;
        }
        if (ch == '#') {
            while (!opStack.isEmpty()) {
                exps.add(opStack.pop() + "");
            }
            return;
        }
        if (isOp(ch + "")) { //运算符还是操作数，操作数直接直加入exps里，运算符进行入栈操作
            if (opStack.isEmpty()) { //运算符栈为空时直接入栈
                opStack.push(ch);
            } else { //否则和栈顶元素比较
                char c = opStack.getFirst();
                if (ch == ')') {  // 如果被处理操作符是 ')'，将opStack里的元素出栈并添加到exps里，直到碰到'('。'(' 和')'直接抛弃
                    for (char c1 = opStack.pop(); c1 != '('; c1 = opStack.pop()) {
                        exps.add(c1 + "");

                    }
                } else if (ch == '(' || compare(ch, c) > 0) { // 如果被处理操作符是'('或者优先级比栈顶元素高，直接入栈
                    opStack.push(ch);
                } else { //如果被处理操作符是非括号，并且优先级不高于栈顶元素（包括等于），将栈顶元素出栈，并加入到exps里，直到被处理操作符高于栈顶元素
                    for (char c1 = opStack.getFirst();
                         compare(ch, c1) <= 0 && !opStack.isEmpty();) {
                       c1 = opStack.pop();
                        exps.add(c1 + "");
                    }
                    opStack.push(ch); //将被处理操作符入栈
                }
            }

        } else {
            exps.add(ch + "");
        }
    }

    private int compare(char c1, char c2) {
        return opValue(c1) - opValue(c2);
    }

    private int opValue(char ch) {
        switch (ch) {
            case '+':
                return 1;
            case '_':
                return 1;
            case '*':
                return 2;
            case '/':
                return 2;
            //            case '(':
            //                return 3;
            default:
                return 0;
        }
    }

    /**
     * 计算逆波兰表达式
     * @return
     */
    public Double exec() {
        while (!exps.isEmpty()) {
            String o = exps.pop();
            if (isOp(o)) {
                Double v1 = execStack.pop();
                Double v2 = execStack.pop();
                Double v3 = calculate(v1, v2, o);
                if (v3 != null) {
                    execStack.push(v3);
                }
            } else {
                execStack.push(Double.parseDouble(o));
            }
        }
        return execStack.pop();
    }

    private Double calculate(Double v1, Double v2, String op) {
        if ("+".equals(op)) {
            return v1 + v2;
        }
        if ("-".equals(op)) {
            return v2 - v1;
        }
        if ("*".equals(op)) {
            return v2 * v1;
        }
        if ("/".equals(op)) {
            return v2 / v1;
        }
        return null;
    }

    private boolean isOp(String ch) {
        return "+".equals(ch) || "-".equals(ch) || "*".equals(ch) || "/".equals(ch)
                || "(".equals(ch) || ")".equals(ch);
    }

    public static void main(String[] args) {
        Express express = Express.create("5 + ((1 + 2) * 4)- 3");
        System.out.println((5 + ((1.0 + 2) * 4) - 3));
        System.out.println(express.exec());
    }
}

编辑于 2015-07-04 14:42:15 回复(0)
叶韵头像 叶韵

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * 实现字符串输入之后的四则运算
 * @author Administrator
 *
 */
public class Math {
 
 public static void main(String[] args) throws IOException {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  resultShow(br);
//  System.out.println(9-7*8);
//  System.out.println(getResult("9-7*8"));
 }
 
 public static void resultShow(BufferedReader br) throws IOException{
  System.out.print("请输入计算式：");
  //开始接受用户指令
  String str = br.readLine();
  try {
   double result = getResult(str);
   if((double)0 == result - (int)result){
    System.out.println("计算后得出的结果为："+(int)result);
   }else{
    System.out.println("计算后得出的结果为："+result);
   }
  } catch (Exception e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
   System.out.println("您输入的公式不正确！请重新输入");
   resultShow(br);
  }
 }
 
 /**
  * 首先将计算式转换为Object数组，数字转为int，符号为String
  * @param expr
  * @return
  */
 public static double getResult(String expr){
  //转换char数组
  char[] cs = expr.toCharArray();
  //转换后存放公式内容的容器
  List<Object>intData = new ArrayList<Object>();
  //这个对象用来存放一串连续数字的char字符
  List<Character> temp = new ArrayList<Character>();
  for (int i = 0; i < cs.length; i++) {
   if((int)cs[i] - 48 < 0 && (int)cs[i]-48 != -2){//判断是否为符号
    intData.add(cs[i]+"");
    temp.clear();
   }
   //判断如果是数字且当前是最后一位或者下一个char字符是符号，结束连续数字判断，转换连续数字为int，并添加到转换后的容器
   else if((int)cs[i] - 48 >= 0 && (i==cs.length-1 || ((int)cs[i+1] - 48 < 0 && (int)cs[i+1]-48 != -2))){
    temp.add(cs[i]);
    intData.add(getCharDouble(temp));
   }
   else{//非以上两种情况，则认为下个char字符也为数字，直接添加到临时变量
    temp.add(cs[i]);
   }
  }
  return getActualResult(intData.toArray());
 }
 
 /**
  * 拼接连续数字并转换为int
  * @param temp
  * @return
  */
 public static double getCharDouble(List<Character> temp){
  String s = "";
  for (Iterator i = temp.iterator(); i.hasNext();) {
   Character character = (Character) i.next();
   s += character;
  }
  
  return Double.parseDouble(s);
 }
 
 public static double getActualResult(Object[] cs){
  return kuohaoMath(cs);
 }
 
 /**
  * 带括号计算，使用递归
  */
 public static  double kuohaoMath(Object[] cs){
  //找到扩号符的索引，正反括号
  int[] indexe敏感词indKuohaoIndex(cs);
  if(indexes != null){
   Object[] temp = new Object[indexes[1]-indexes[0]-1];
   //截获括号里面的内容数组
   for (int i = 0; i < temp.length; i++) {
    temp[i] = cs[indexes[0]+1+i];
   }
   //然后开始计算括号里面的值
   double result = normalMath(temp);
   //计算完成后添加到新容器，并递归继续找括号
   List<Object> tempData = new ArrayList<Object>();
   for (int i = 0; i < cs.length; i++) {
    if(i == indexes[0]){
     tempData.add(result);
    }else if(i<indexes[0] || i > indexes[1]){
     tempData.add(cs[i]);
    }
   }
   
   return kuohaoMath(tempData.toArray());
  }else{
   //如果无括号则直接返回普通计算值
   return normalMath(cs);
  }
 }
 
 /**
  * 首先需要找到最里层括号的索引
  */
 public static int[] findKuohaoIndex(Object[] cs){
  int[] indexes = null;
  for (int i = 0; i < cs.length; i++) {
   //从头开始找，先找最近的反括号
   if(cs[i].equals(")")){
    indexes = new int[2];
    indexes[1] = i;
    //然后去找最近的正括号
    for (int j = i-1; j >=0; j--) {
     if(cs[j].equals("(")){
      indexes[0] = j;
      break;
     }
    }
    break;
   }
  }
  
  return indexes;
 }
 
 /**
  * 不包括括号运算的，普通运算算法
  */
 public static double normalMath(Object[] cs){
  int index = -1;
  //先乘法或除法，找到*,/的索引位置
  index = findMultiplication(cs);
  if(index >= 0){
   List<Object> tempData = new ArrayList<Object>();
   //计算符号附近相邻值得结果
   double result = 0;
   if(cs[index].equals("*")){
    result = (Double)cs[index-1] *  (Double)cs[index+1];
   }else{
    result = (Double)cs[index-1] / (Double)cs[index+1];
   }
   //添加到新容器
   for (int i = 0; i < cs.length; i++) {
    if(i != index - 1 && i != index +1 && i != index){
     tempData.add(cs[i]);
    }else if(i == index){
     tempData.add(result);
    }
   }
   //继续向下递归
   return normalMath(tempData.toArray());
  }
  //如果没有乘法和除法了，那么开始加减算法，原理与乘法相同
  index = findAdd(cs);
  if(index >= 0){
   List<Object> tempData = new ArrayList<Object>();
   //计算符号附近相邻值得结果
   double result = 0;
   if(cs[index].equals("+")){
    result = (Double)cs[index-1] +  (Double)cs[index+1];
   }else{
    result =  (Double)cs[index-1] -  (Double)cs[index+1];
   }
   for (int i = 0; i < cs.length; i++) {
    if(i != index - 1 && i != index +1 && i != index){
     tempData.add(cs[i]);
    }else if(i == index){
     tempData.add(result);
    }
   }
   return normalMath(tempData.toArray());
  }
  //计算出最终结果时，只有一个值了
  return (Double) cs[0];
 }
 
 /**
  * 查找数组中加减的符号位置
  */
 
 public static int findAdd (Object[] cs){
  for (int i = 0; i < cs.length; i++) {
   if(cs[i].equals("+") || cs[i].equals("-")){//-5是加号，-3是减号
    return i;
   }
  }
  
  return -1;
 }
 
 /**
  * 查找数组中乘除的符号位置
  */
 
 public static int findMultiplication (Object[] cs){
  for (int i = 0; i < cs.length; i++) {
   if(cs[i].equals("*") || cs[i].equals("/")){
    return i;
   }
  }
  
  return -1;
 }
}

发表于 2015-05-28 20:41:12 回复(0)
周波头像 周波
我用java实现
//f1处理输入字符串，采用递归的方式处理 括号优先级问题。
String f1(String str){
int index=str.indexOf("(");
int fIndex=str.lastIndexOf(")");
if(index>=0&&fIndex>=0){
String str1=str.subString(0,index);
String str2=str.subString(index,fIndex);
String str3=str.subString(fIndex);
str2=f1(str2);
str=str1+str2+str3;
}
return cal(str);
}

//cal将减号变成负号，加减则都是 加号，再split分割。分割后的数组是乘或除，再调用函数下面的处理
String cal(String str){
//   * /    + -
float sum=0;
String strA[]=str.split("-");
str=null;
for(int i=0;i<strA.length;i++){
if(i<strA.length-1) strA[i]=strA[i]+"+-";

str+=strA[i];
}

String strA2[]=str.split("+");
for(int i=0;i<strA2.length;i++){
//处理分割后的乘除字符串，并运算，变为float
strA2[i]=calChenAndChu(strA2[i]);
sum+=StringToFloat(strA2[i]);
}

return FloatToString(sum);
}
//处理乘除
String calChenAndChu(String str){
//按*分割，成除法字符串，或者 单个float字符
String strA[]= str.split("*");
float num=1;
for(int i=0;i<strA.length;i++){

if(strA[i].indexOf("/")>0) strA[i]=calChu(strA[i]);//如果除，则计算除
num*=StringToFloat(strA[i]);
}
return  FloatToString(num);
}
//处理除
String calChu(String str){
 String strA[]= str.split("/");
float num;
for(int i=0;i<strA.length;i++){
if(i>0)
num/=StringToFloat(strA[i]);
else
num=StringToFloat(strA[i]);
}
return  FloatToString(num);
}


public static void main(String args[]) { 
          Scanner input = new Scanner(System.in);
        String val = null;       // 记录输入的字符串
            System.out.print("请输入：");
            val = input.nextLine();   

  try{  //以上方法皆未捕捉异常，这里进行捕捉一下，更严谨一些
        System.out.println("结果是："+f1(val));
   }catch{
   System.out.println("输入有误");
  }
        input.close(); // 关闭资源
    }
 }

发表于 2015-04-27 17:39:39 回复(0)
牛客504013号头像 牛客504013号
我是用C#实现的：
private void button1_Click(object sender, EventArgs e)
        {
            string text = this.textBox1.Text.Trim();
            char[] charArray = text.ToCharArray();
            List<string> stringArray = charToList(charArray);
            int cacuResult = caculateExpression(stringArray);
            textBox2.Text = cacuResult.ToString();
        }

        //数据预处理
        /*
         因为表达式【(1+2)*3*(23+6)/9+4】中包含数字23，被转化为char数组后，2和3是分开的，所以要合并到一起
         */
        private List<string> charToList(char[] charArray)
        {
            List<string> result = new List<string>();
            string[] opreators = new string[] { "+", "-", "*", "/", "(", ")" };

            string temp = "";
            for (int i = 0; i < charArray.Length; i++)
            {
                string item = charArray[i].ToString();
                if (opreators.Contains(item))
                {
                    if (temp != "")
                    {
                        result.Add(temp);
                        temp = "";
                    }
                    result.Add(item);
                }
                else
                {
                    temp += item;
                }
            }

            //最后结尾的一定是数字或者括号，如果是数字，则要加上
            if (temp != "")
            {
                result.Add(temp);
            }

            return result;

        }

        //计算简单表达式的值，这个方法只适合不带括号的简单表达式的计算
        private int caculateSimpleExpression(List<string> charArray)
        {
            int result = 0;

            //要考虑【乘法】和【除法】的优先级
            //优先计算【乘法】和【除法】
            string[] opreatorArray = new string[] { "*", "/", "+", "-" };

            for (int i = 0; i < opreatorArray.Length; i++)
            {
                string opreator = opreatorArray[i];
                int multIndex = charArray.IndexOf(opreator);
                while (multIndex != -1)
                {
                    //前一位元素、后一位元素应该都是整数，直接运算
                    int tempCacu = 0;
                    if (opreator == "*")
                    {
                        tempCacu = Convert.ToInt32(charArray[multIndex - 1]) * Convert.ToInt32(charArray[multIndex + 1]);
                    }
                    else if (opreator == "/")
                    {
                        tempCacu = Convert.ToInt32(charArray[multIndex - 1]) / Convert.ToInt32(charArray[multIndex + 1]);
                    }
                    else if (opreator == "+")
                    {
                        tempCacu = Convert.ToInt32(charArray[multIndex - 1]) + Convert.ToInt32(charArray[multIndex + 1]);
                    }
                    else if (opreator == "-")
                    {
                        tempCacu = Convert.ToInt32(charArray[multIndex - 1]) - Convert.ToInt32(charArray[multIndex + 1]);
                    }
                   
                    //算出的结果重新塞入数组中运算符的位置，并且移除已经运算过的数值
                    charArray[multIndex] = tempCacu.ToString();
                    charArray.RemoveAt(multIndex - 1);//前一位
                    charArray.RemoveAt(multIndex);//因为移除前一位之后，后一位的索引发生变化
                    //接着计算其他的乘法运算符
                    multIndex = charArray.IndexOf(opreator);
                }
            }

            //计算应该是栈顶的元素，返回即可
            result = Convert.ToInt32(charArray[0]);

            return result;
        }

        //包含括号的表达式的值计算
        private int caculateExpression(List<string> charArray)
        {
            int result = 0;
            //如果表达式不包含括号，则认为是简单表达式，直接返回结果
            if (charArray.IndexOf("(") == -1)
            {
                result = caculateSimpleExpression(charArray);
                return result;
            }

            //处理括号问题
            while (charArray.IndexOf("(") != -1)
            {
                //有多少个左括号，一定就有多少个右括号与之对应

                //按照左括号的位置从右往左计算
                int leftIndex = 0;//位置最靠右的左括号
                int tempIndex = charArray.IndexOf("(");
                while (tempIndex != -1)
                {
                    leftIndex = tempIndex;
                    tempIndex = charArray.IndexOf("(", leftIndex + 1);
                }

                int rightIndex = charArray.IndexOf(")", leftIndex + 1); ;//找出离该左括号最近的右括号

                List<string> tempStringArray = new List<string>();//暂存数组
                //左括号和右括号之间的元素，我们放入到暂存数组里面，这里面应该是一个简单表达式。可以直接计算
                for (int i = leftIndex + 1; i < rightIndex; i++)
                {
                    tempStringArray.Add(charArray[i]);
                }

                int tempResult = caculateSimpleExpression(tempStringArray);//暂存数组中简单表达式的值
                //将计算出来的值塞入数组中左括号的位置，同时移除计算过的简单表达式【包含右括号】
                charArray[leftIndex] = tempResult.ToString();
                for (int i = leftIndex + 1; i <= rightIndex; i++)
                {
                    charArray.RemoveAt(leftIndex + 1);
                }
            }

            //解决括号问题之后，剩下的应该就是简单表达式了
            result = caculateSimpleExpression(charArray);
            return result;
        }
发表于 2015-04-25 19:20:02 回复(0)
机器变得更残忍头像 机器变得更残忍
用栈，两个栈，一个存数字，一个存操作符，根据操作符的优先级来进行进栈和出栈的操作
发表于 2015-04-25 13:59:15 回复(0)
MyGoodHelper头像 MyGoodHelper
逆波兰表达式
发表于 2015-01-08 12:57:11 回复(0)
提交观点

问题信息

微软 字符串 小米集团 复杂度 C++ Java
上传者：emma默默
难度：
9条回答 34236浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号